- Section 3.2
- Address tape?
- By numbering options at each nondeterministic choice, records what choices have
been made in current computation
- By numbering options at each nondeterministic choice, records what choices have
been made in current computation
- Alternative but equivalent forms of Turing machine
- “Robustness” = ability to make equivalent alternatives
- Multitape machines are equivalent to machines with 1 tape
- Multitape good for designing machines
- Nondeterministic machines equivalent to multitape
- And thus to single-tape
- How to convert between models
- Enumerators?
- Computing model that focuses on generating strings in a language rather than accepting/rejecting them
- But also equivalent to Turing machines
- Address tape?
- Other variations
- Doubly-infinite tape
- Can be simulated by standard semi-infinite tape in several different ways
- Can be simulated by standard semi-infinite tape in several different ways
- Can also have a 2-dimensional tape
- Turing machines that can write to tape or move but not both in a single transition
- Simulate standard Turing machine in this model by expanding every standard transition into two, a first one that writes and a second that moves
- Doubly-infinite tape
- The Church-Turing Thesis
- Read section 3.3