Turing Machines

A Turing machine is a theoretical model of computation proposed by Alan Turing in 1936. It is not a real device — it is a mathematical model that defines what it means for a function to be computable.

A Turing machine consists of:

Component	Description
Tape	An infinite sequence of cells, each holding one symbol; extends infinitely in one direction
Read-write head	Reads the current cell; can write a new symbol to it; moves left or right one cell
Finite set of states ($Q$)	The machine is always in exactly one state; includes a start state and halting states
Alphabet ($\Sigma$)	Finite set of symbols the tape can contain; includes a special blank symbol ($B$ or $\bigsqcup$)
Transition function ($\delta$)	Defines what the machine does in each (state, symbol) situation

Start state: the machine begins in a designated start state with the input written on the tape.

Halting states: states with no outgoing transitions. When the machine enters a halting state, it stops. There may be an accept state and a reject state.

The transition function $\delta$ is the heart of a Turing machine. For each combination of current state and current symbol, it specifies:

1. The new state to transition to
2. The symbol to write on the current cell (may be the same as the current symbol)
3. The direction to move the head: Left (L) or Right (R)

$\delta (q,s)\to (q^{\prime },s^{\prime },D)$

where $q$ = current state, $s$ = current symbol, $q^{\prime }$ = new state, $s^{\prime }$ = symbol to write, $D\in \{L,R\}$.

Example entry:

$\delta (q_0,0)\to (q_1,1,R)$

Meaning: in state $q_0$, reading symbol 0 → write 1, move right, enter state $q_1$.

The transition function can be represented as:

• A transition table (rows = states, columns = input symbols)
• A state transition diagram (circles = states, labelled arrows = transitions)

Machine: flip all 0s to 1s and all 1s to 0s on a tape, then halt

Alphabet: $\{0,1,B\}$ where $B$ = blank

State	Symbol read	Write	Move	New state
$q_0$	0	1	R	$q_0$
$q_0$	1	0	R	$q_0$
$q_0$	$B$	$B$	R	$q_H$ (halt)

State transition diagram:

          0 → write 1, R
          1 → write 0, R
          ┌─────────────┐
          ↓             │
    ──→  (q₀) ─────────┘
          │
          │ B → write B, R
          ↓
         (qH)   ← halting state

Trace — input tape: 0 1 1 0 B …

Step	State	Head pos	Tape	Action
1	$q_0$	1	0 1 1 0 B	read 0 → write 1, R
2	$q_0$	2	1 1 1 0 B	read 1 → write 0, R
3	$q_0$	3	1 0 1 0 B	read 1 → write 0, R
4	$q_0$	4	1 0 0 0 B	read 0 → write 1, R
5	$q_0$	5	1 0 0 1 B	read B → write B, R
6	$q_H$	6	1 0 0 1 B	halt

Output: 1 0 0 1 (all bits flipped) ✓

When tracing a Turing machine step by step:

1. Look up the current state and the symbol under the head in the transition table
2. Write the new symbol to the current cell
3. Move the head left or right as specified
4. Transition to the new state
5. Repeat until a halting state is reached (or it becomes clear the machine will not halt)

Machine: add 1 to a binary number

Alphabet: $\{0,1,B\}$. The tape holds the binary number. The head starts at the rightmost digit.

State	Read	Write	Move	New state
$q_0$	1	0	L	$q_0$ (carry: keep flipping 1s to 0s)
$q_0$	0	1	R	$q_H$ (no carry: write 1, done)
$q_0$	$B$	1	R	$q_H$ (overflow: write leading 1)

Trace — adding 1 to 1 0 1 (head starts at rightmost digit, position 3):

Step	State	Head	Tape	Action
1	$q_0$	3	1 0 1	read 1 → write 0, L
2	$q_0$	2	1 0 0	read 0 → write 1, R
3	$q_H$	3	1 1 0	halt

Result: 1 1 0 = 6 in binary. Input was 1 0 1 = 5. Correct: 5 + 1 = 6. ✓

A Universal Turing Machine (UTM) is a Turing machine that can simulate any other Turing machine.

A UTM takes two inputs on its tape:

• An encoding of the Turing machine $M$ to simulate (its states, alphabet, and transition function)
• The input to be processed by $M$

The UTM then simulates $M$ step by step on that input, producing the same output as if $M$ had run directly.

Why the UTM matters:

1. It defines computability — a function is computable if and only if a Turing machine (and therefore a UTM) can compute it
2. It is the theoretical model for the stored-program computer — a real computer executes a program (the encoding of the machine) stored alongside data (the input), just as a UTM simulates $M$ with $M$'s description on the same tape
3. It underpins the halting problem — Turing used the UTM to prove the halting problem is unsolvable

The Church-Turing thesis states that any function computable by any algorithm can be computed by a Turing machine. This means Turing machines define the absolute boundary of what is computable.

1. Forgetting that halting states have no outgoing transitions

A halting state is defined by having no transitions — the machine simply stops. A state that has some transitions is not a halting state even if it could eventually be reached from itself.

2. Confusing the Turing machine with the UTM

An ordinary Turing machine solves one specific problem. A Universal Turing Machine can simulate any other Turing machine. They are different machines.

3. Getting the transition notation wrong

$\delta (q,s)\to (q^{\prime },s^{\prime },D)$ has five components: current state, current symbol, new state, symbol to write, direction. Missing the direction or confusing write-symbol with move-direction loses marks in transition table questions.

4. Stating that a Turing machine can compute anything

Turing machines can compute exactly the computable functions. The halting problem is an example of a non-computable function — no Turing machine can solve it for all inputs.