Notes - Pages 151-193

Turing Machine conf
As a Turing machine computes, changes occur in the current state, the current tape contents, and the current head location. A setting of these three items is called a configuration of the Turing machine
168
Types of configurations
Start, accept, reject configurations... the latter two are halt configurations. A turing machine accepts if there is a incremental series of configurations from the starting configuration to a accepting configuration
169
Deciders
A Turing Machine that rejects on all inputs is called a Decider because it does not loop, thus it can never loop indefinetly and will always enter a halting state.
170
Invariant TM models
invariance to certain changes in the definition, proved by showing that one can simulate the other. Remarkably, all models with unrestricted access to infinite memory turn out to be equivalent in power, so long as they satisfy reasonable requirements (see pg 181)
176
ND-TM === D-TM
Similar to DFA === NFA, interesting given the similarity to PDA
178
TM descriptions categories
formal (6 tuple), implementation: use english to describe how a TM head and tape changes, high-level english psuedo-code/algorithm description
185-186

This chapter introduced the basics of turing machines, the important concepts include what is turing decidable, turing recognizable, non-deterministic turing machines have the same computing ability as deterministic turing machines. The variants of turing machines with unrestricted access to infinite memory under reasonable requirements (only one specified was finite work in single step) are equivalent in power regardless of variant.