Next: Church Turing Thesis:(1936) Up: Lecture One(On Aug 25, Previous: History
Idea: Finite State Machine that ask for as much memory as it needs. That is, finite state, but unbounded memory.
Simplest One: Change 0s to 1s in the input.
| state | Tape Symbol | New State | New tape Symbol | Tape Direction |
 |
0 | |
1 | right |
|
1 | |
1 | right |
|
space |  |
space | stay |
Key point: Computation is local in some sense5.