Turing Machines

the formal definition of a Turing machine

A formal definition is just a precise parts list: it names every piece of the machine so that two people anywhere in the world build exactly the same thing from the description. Where a DFA was a five-tuple (states, alphabet, transition, start, accept), a Turing machine needs a little more because it has a richer alphabet and TWO ways to halt with an answer. The complete recipe is usually written as a seven-tuple.

The seven pieces are: Q, a finite set of states; Σ (Sigma), the input alphabet (the symbols the input may use, never including the blank); Γ (Gamma), the tape alphabet, which contains Σ and also the blank and any working symbols; δ (delta), the transition function mapping (state, scanned symbol) to (next state, symbol-to-write, move-left-or-right); q0, the start state where computation begins with the head on the leftmost input symbol; q_accept, a special state that immediately halts and accepts; and q_reject, a special state that immediately halts and rejects (with q_accept and q_reject being different states). Put together: M = (Q, Σ, Γ, δ, q0, q_accept, q_reject).

The two halting states, accept and reject, are the real novelty compared to a DFA. A DFA decides by checking which state it ends in after reading all input; a Turing machine instead halts the instant it enters q_accept or q_reject, possibly long before any 'end of input' (and it might also never reach either, and loop). This is why a Turing machine can have three outcomes, not two. The definition is deliberately minimal: every later convenience (extra tapes, a 'stay' move, nondeterminism) can be simulated by a machine of this plain form, so the seven-tuple is the bedrock all the variants reduce back to.

A machine recognizing strings of 0s and 1s with an even number of 1s might be M = (Q, Σ, Γ, δ, q0, q_accept, q_reject) with Q = {q0, q1, q_accept, q_reject}, Σ = {0, 1}, Γ = {0, 1, B}, and δ flipping between q0 and q1 on each 1 and entering q_accept on reading B from an even state.

The seven-tuple: Q, Σ, Γ, δ, q0, q_accept, q_reject.

Σ never contains the blank, but Γ always does, and Σ is a subset of Γ. Conventions vary slightly (some use a single 'halt' state plus an output convention), but the essential extras over a DFA are the tape alphabet and two halting states.

Also called
seven-tupleTM 7-tuple圖靈機七元組七元組定義