Chapter 3 · Turing Machines

The Turing machine model

The Turing machine is the model that defines computation itself. It has an unbounded tape it can both read and write, and a head that moves left or right.

Definition · Turing machine

A TM is a 7-tuple (Q, Σ, Γ, δ, q₀, q_accept, q_reject) where the transition function both moves the head and rewrites the tape:

δ : Q × Γ → Q × Γ × {L, R}
The Church–Turing thesis
Every model of computation anyone has devised — multi-tape machines, nondeterministic machines, λ-calculus, your laptop — is equivalent in power to this one. “Algorithm” just means “Turing machine.”
Check your understanding

1. What distinguishes a Turing machine from a PDA?

2. The Church–Turing thesis claims that…

answer all 2 to submit