Turing Machine Basics

Turing Machine Basics

A Turing machine (TM) is the most powerful computational model in the Chomsky Hierarchy. It consists of an infinite tape, a read/write head that moves left or right, a state register, and a set of transition rules. Alan Turing invented it in 1936 to formalize the concept of "computation" itself.

Anything that can be computed by any algorithm can be computed by a Turing machine. This is the Church-Turing thesis — the TM is the universal model of computation.

Formal Definition

A Turing machine is a 7-tuple M = (Q, Σ, Γ, δ, q0, qaccept, qreject), where:

Q       — finite set of states
Σ       — input alphabet (does not include blank)
Γ       — tape alphabet (includes blank symbol ␣)
δ       — transition function
          Q × Γ → Q × Γ × {L, R}
q0      — start state
qaccept — accept state
qreject — reject state (qaccept ≠ qreject)

A transition δ(q, a) = (p, b, D) means:
  In state q, reading symbol a on tape:
  Write b on the tape, move head in direction D
  (L = left, R = right), and enter state p.

If δ(q, a) is undefined, the machine halts and rejects.

How It Works

The tape is initially loaded with the input string, with the rest of the tape filled with blanks. The head starts at the leftmost input symbol. At each step, the machine reads the tape symbol under the head, looks up the transition rule, writes a new symbol, moves the head, and changes state.

The machine halts when it enters qaccept (accept) or qreject (reject), or when no transition is defined (reject).

Example: TM that adds 1 to a binary number

Input: "1101" on tape

Step 1: Move right to find the rightmost digit
Step 2: If digit is 0, write 1 and halt (accept)
Step 3: If digit is 1, write 0 and carry 1 left
Step 4: If at the leftmost position and carrying 1,
        write 1 and halt (accept)

Trace for "1101":
  1101 → 1110 (carry propagated)
  
The TM handles carries correctly because it can
move left and right on the tape.

Variants

Several TM variants exist, all equivalent in power:

1. Multi-tape TM:
   Multiple tapes, each with its own head.
   Equivalent to single-tape TM (simulated with
   polynomial overhead).

2. Nondeterministic TM (NTM):
   Multiple possible transitions from each state.
   Equivalent to deterministic TM for decidability
   (but may differ in time complexity).

3. Universal TM:
   A TM that can simulate any other TM given its
   description and input. This is the theoretical
   basis for programmable computers.

4. Enumerators:
   A TM that prints all strings in a language
   on a separate output tape.