title: "Turing Machine"

Turing Machine

Definition. A Turing machine is a seven-tuple $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$ where $Q$ is a finite set of states, $\Sigma$ the input alphabet, $\Gamma \supseteq \Sigma$ the tape alphabet containing a blank $\sqcup \notin \Sigma$, and $\delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$ the transition function.

The machine works on a tape that is unbounded, writable at any position, and traversable in both directions, which is what separates it from the PDA whose stack is readable only at the top and destroyed by reading. On any input it accepts, rejects, or runs forever, and that third outcome is what splits decidable from Turing-recognizable. Defined in Lecture 6; by the Church-Turing thesis it captures the informal notion of an algorithm.