COGSCI 200 Lecture 10: LEC 10_ Computation Part 1 - Turing Machine
13 Jun 2018
School
Department
Course
Professor
Computation PART 1: Turing Machine
Video: A Turing Machine that Does Addition
I. Five Primitives of Computations
A. Maintain a tape on which symbols are recorded
B. Maintain a list of symbols, where this list is finite
C. Read/Write/Erase symbols on the tape
D. Maintain a state memory, i.e. a memory of internal states
E. Follow simple instructions in a finite transition table, where the instructions are the
following form
*If you are in so-and-so state and you read so-and-so symbol, then write so-and-so symbol on
the tape, move right or left, and change to so-and-so state
II. Renee Descartes
A. MIND (thinking thing) is entirely distinct from BODY (extended thing)
B. According to cogsci, “Thinking is computation”
III. Sciences make processes when they figure out the fundamentals - the primitive objects xxxxxxxx
- xxxxx
A. Ff
IV. Computation consists in the execution of algorithms
A. An algorithm is … → Simple, mechanical
1. It maps one set of symbols
2. It is finitely specified
3.
a) They can be executed on Turing machines
b) They do NOT require substantial intelligence
B. The function can be defined over an infinite domain
V. Computation Questions→ Turing answered these!
A. What are the primitive “building blocks” of computation?
1. ???
B. What can you construct from the primitives?
1. ???
2. ???
C. What are the limits on what you can construct?
VI. Turing Machine depends on…
A. What is on the tape, AND
B. What state it is in, AND
C. What instructions are in its transition tape
VII. The set of states of the Turing machine’s state memory can be in any of a (finite) xxxx?
A. The tape is only 1 and 0
find more resources at oneclass.com
find more resources at oneclass.com
