Appendix B - Turing machines

Summary

Turing machines

This appendix is based on [Pap94] and it is recommended that the reader refer to that for detailed exposition on Turing machines, and computational complexity.

Intuitively, a deterministic Turing machine (DTM) is an automata bundled with a semi-infinite tape with a cursor to read from and write to. So, like an automata, there is a state and state transitions are based on the current state and what the cursor points to on the tape. But in addition to the state transition, there is an accompanying transition that dictates if the symbol in the tape location pointed to by the cursor should be overwritten and if the cursor should move to the left or right – by one cell – of its current position. Special symbols mark the beginning of the tape (>), the end of the input on the tape (⊔), and the output of the computation (‘halt’, ‘yes’, ‘no’). We now give a formal definition of DTMs.

Definition 151 A DTM is a quadruple M = (S, Σ, δ, s₀) where S is a finite set of nonfinal states that includes s₀ the initial state, Σ is a finite alphabet of symbols including the special symbols > and ⊔, and δ is a transition function that maps S × Σ to S ∪ {halt, yes, no} × Σ × {←, →, –}

Intuitively, δ is the control (or the program) of the machine that dictates how the machine behaves.