ClassicalComputation.pdf

As you come in: Sign in for attendance: Complete the quiz: Download AttendanceRadar Login with Public Server Select STUDENT Register/login by email, with your school email Select “Scan and mark attendance” If you have issues, come to the...

As you come in: Sign in for attendance: Complete the quiz: Download AttendanceRadar Login with Public Server Select STUDENT Register/login by email, with your school email Select “Scan and mark attendance” If you have issues, come to the front and we can manually mark you as present Classical Computation  What is a computer? How can we model the computations of the mind? Antikythera mechanism (c. 100BC) Antikythera mechanism (c. 100BC)  One of the first “computers” Not a general-purpose computer (not programmable)  Charles Babbage: Difference Engine (1822-1849)  Charles Babbage: Analytical Engine (1833-)  First “computer program”: algorithm for using the Analytical engine to compute Bernoulli numbers Ada Lovelace What shall we do to get rid of Mr. Babbage and his calculating Machine? Surely if completed it would be worthless as far as science is concerned? —British Prime Minister Sir Robert Peel  “[The Analytical Engine] might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations…” Ada Lovelace  “In enabling mechanism to combine together general symbols, in successions of unlimited variety and extent, a uniting link is established between the operations of matter and the abstract mental processes of the most abstract branch of mathematical science.” Ada Lovelace A general-purpose calculator can manipulate symbols that represent abstract processes Alan Turing (1912-1954) https://informationisbeautiful.net/visualizations/based-on-a-true-true-story/  Turing machines A “Turing machine” is a theoretical system with: An infinitely long “tape” of memory where symbols can be written and read A current position on the tape and a current state A lookup table for what to do next, based on the machine’s state and the symbol at the current position Church-Turing Thesis: Any computation that a human could carry out with pencil and paper can also be done by a Turing machine Are there an even number of “1”s in this number? 1001011 https://turingmachine.io/ input: '100101' blank: ' ' start state: even table: even: 1: {R: odd} 0: {R: even} ' ': {R: decide_even} odd: 1: {R: even} 0: {R: odd} ' ': {R: decide_odd} decide_even: decide_odd: Incrementing numbers Decimal numbers: Binary numbers: 484 484 + 1 485 101 101 + 1 100 489 489 110 + 1 480 490 input: '0011' blank: ' ' start state: right table: right: [1,0]: R ' ' : {L: carry} carry: 1 : {write: 0, L} [0,' ']: {write: 1, L: done} done: Turing machine summary A Turing machine can carry out any computation that a human could accomplish by following a series of steps Creating a Turing machine to carry out a computation requires us to specify a representation as well as an algorithm (series of rules) This is at the middle (algorithmic/representational) of Marr’s levels – how can we implement a Turing machine?  Richard Ridel Rules Tape symbols implemented implemented as with pegs on a peg positions square board  Richard Ridel Start state: 0011_ End state: 0100_ Rothemund 1995  McCulloch & Pitts, 1943 N1(t-1) AND NOT N2(t-1) = N3(t) This “NAND” operation is universal i.e. we can build any logical operations out of it Therefore we can implement any logical function in neurons Therefore we can implement a Turing machine in neurons  Classical computational theory of mind: The mind is a computational system, with core mental processes that use algorithms and representations similar to a Turing machine According to CCTM, the mind is a Turing-style computing system (not “like” a computing system) Memory representations are discrete symbols Algorithms consist of a sequence of steps Does allow for non-traditional elements: Allowing memory access beyond left/right movements Allowing for parallel computation Allowing for probabilistic transitions  Example: ACT-R cognitive theory Declarative memory Procedural memory If: 3+3→6 Observe X + Y 3+4→7 Then: 484 Attempt to activate a +311 8+1→9 fact matching X+Y→Z 5 6+7→13 If: Goal = adding a column 8-1→7 with X and Y and fact with →Z is active 1+2→3 Then: Write ones place of Z 6-2→4 Activate carry goal if Z > 9  Example: ACT-R cognitive theory Declarative memory Procedural memory If: 3+3→6 Observe X + Y 3+4→7 Then: 484 Attempt to activate a +311 8+1→9 fact matching X+Y→Z 5 6+7→13 If: Goal = adding a column 8-1→7 with X and Y and fact with →Z is active 1+2→3 Then: Write ones place of Z 6-2→4 Activate carry goal if Z > 9 CCTM: Answer to Dualism? René Descartes’ Dualism: matter and mind are two distinct kinds of substances CCTM provides an account of how thinking can arise from information processing, which can be implemented in physical objects If the mind is a computing system, then minds can arise purely from physical implementations  We can build a Turing machine to carry out any specific computation Can we create a “Universal” Turing Machine, that takes a description of a Turing Machine as input on its tape and then runs that Turing Machine?  A general-purpose computer Turing proved that it is possible to construct a Universal Turing Machine This is a truly general-purpose computer: with the right inputs, it can carry out any possible computation Caveat: the UTM is very inefficient at carrying out some kinds of operations Von Neumann architecture  Is the mind a general-purpose programmable computer?  Is the mind a general-purpose programmable computer? Yes, in some sense – basically by definition, humans can be given instructions to compute anything computable But many specific mental processes are likely not programmable, and instead implement fixed learning algorithms that can be used to acquire new skills and information Alternatives to CCTM Must mental representations be symbolic? Must mental algorithms consist of sets of rules that are applied in steps? Connectionism rejects both these ideas… Reminders Next time: Neural Network Computation Short paper proposal #1 due Oct 3rd – start thinking of possible topics, see Courseworks for suggestions