Turing Machines

A Turing machine is a theoretical model of computation invented by Alan Turing in 1936. It is the most powerful abstract model of computation and forms the foundation of theoretical Computer Science. The OCR H446 specification requires understanding of how Turing machines work and their significance.

---

What Is a Turing Machine?

A Turing machine consists of:

Component	Description
Tape	An infinite strip divided into cells, each containing a symbol (or blank)
Read/write head	A pointer that reads and writes symbols on the tape, one cell at a time
State register	Stores the current state of the machine (one of a finite set of states)
Transition function	A set of rules that determine what to do based on the current state and the symbol under the head

---

How a Turing Machine Operates

At each step, the Turing machine:

1. Reads the symbol under the read/write head
2. Based on the current state and the symbol read, the transition function specifies:
   • The symbol to write in the current cell (replacing the one that was there)
   • The direction to move the head (Left or Right)
   • The next state to enter
3. Repeat until a halting state is reached (or it runs forever)

---

Formal Definition

A Turing machine is defined as a tuple: (Q, Sigma, Gamma, delta, q0, qaccept, qreject) where:

Symbol	Meaning
Q	Finite set of states
Sigma	Input alphabet (symbols that can appear on the tape initially)
Gamma	Tape alphabet (includes Sigma plus the blank symbol)
delta	Transition function: Q x Gamma -> Q x Gamma x {L, R}
q0	Start state
qaccept	Accept state (halting — the machine accepts the input)
qreject	Reject state (halting — the machine rejects the input)

---

Transition Function

The transition function is the set of rules. Each rule has the form:

delta(current_state, symbol_read) = (next_state, symbol_write, direction)

This is often written in a table:

Current State	Read	Write	Move	Next State
q0	0	1	R	q0
q0	1	0	R	q0
q0	_	_	L	q1
q1	0	0	L	q1
q1	1	1	L	q1
q1	_	_	R	qhalt

Where _ represents the blank symbol.

---

Worked Example: Binary Complement

Task: Design a Turing machine that computes the bitwise complement of a binary string (flip every 0 to 1 and every 1 to 0).

Input tape: ..._ 1 0 1 1 0 _ ... (head starts at leftmost symbol)

Transition rules:

Current State	Read	Write	Move	Next State
q0	0	1	R	q0
q0	1	0	R	q0
q0	_	_	L	qhalt

Trace:

Step	State	Tape (head position in brackets)	Action
0	q0	_ [1] 0 1 1 0 _	Read 1, write 0, move R
1	q0	_ 0 [0] 1 1 0 _	Read 0, write 1, move R
2	q0	_ 0 1 [1] 1 0 _	Read 1, write 0, move R
3	q0	_ 0 1 0 [1] 0 _	Read 1, write 0, move R
4	q0	_ 0 1 0 0 [0] _	Read 0, write 1, move R
5	q0	_ 0 1 0 0 1 [_]	Read _, write _, move L, go to qhalt

Output tape: _ 0 1 0 0 1 _

The complement of 10110 is 01001. Correct.

---

Worked Example: Unary Increment