Turing Machines

A Turing machine is a theoretical model of computation invented by Alan Turing in 1936. Despite being remarkably simple in its design, a Turing machine can simulate any algorithm that any modern computer can execute. It is the most powerful computational model in the Chomsky hierarchy and defines the boundary of what is computable.

---

The Structure of a Turing Machine

A Turing machine consists of:

Component	Description
Infinite tape	Divided into cells, each containing a symbol from the tape alphabet. The tape extends infinitely in both directions.
Read/write head	Points to one cell at a time. Can read the symbol, write a new symbol, and move left or right.
State register	Stores the current state of the machine (from a finite set of states).
Transition function	A set of rules: given the current state and the symbol under the head, specify the symbol to write, the direction to move, and the next state.

---

Formal Definition

A Turing machine is defined as a 7-tuple (Q, Σ, Γ, δ, q₀, qₐ, qᵣ):

Symbol	Meaning
Q	Finite set of states
Σ	Input alphabet (symbols that appear on the tape initially)
Γ	Tape alphabet (includes Σ and the blank symbol □)
δ	Transition function: δ(state, symbol) → (new symbol, direction, new state)
q₀	Start state
qₐ	Accept (halt-accept) state
qᵣ	Reject (halt-reject) state

The machine begins in q₀ with the input written on the tape and the head at the leftmost input symbol. All other cells contain the blank symbol (□).

---

How a Turing Machine Operates

1. Read the symbol under the head.
2. Consult the transition function: δ(current state, current symbol).
3. Write a new symbol to the current cell.
4. Move the head left (L) or right (R).
5. Transition to the next state.
6. Repeat until the machine enters qₐ (accept) or qᵣ (reject).

If no transition is defined for the current state and symbol, the machine halts.

---

Example: Binary Increment

A Turing machine that adds 1 to a binary number (e.g., 1011 → 1100).

States: {q0, q1, qHalt} Tape alphabet: {0, 1, □}

Transition rules:

State	Read	Write	Move	Next State
q0	0	0	R	q0
q0	1	1	R	q0
q0	□	□	L	q1
q1	0	1	L	qHalt
q1	1	0	L	q1
q1	□	1	L	qHalt

Trace: Input "1011"