Turing Machines and the Halting Problem

Turing Machines and the Halting Problem

The Turing machine is the theoretical foundation of all modern computing. Despite its simplicity, it can compute anything that any real computer can compute. The halting problem reveals a fundamental limit: some questions are undecidable — no algorithm can ever answer them.

What is a Turing Machine?

A Turing machine (TM) is an abstract mathematical model of computation, proposed by Alan Turing in 1936. It consists of:

Component	Description
Infinite tape	Divided into cells, each holding one symbol (or blank). Extends infinitely in both directions
Read/write head	Points at one cell at a time; can read the symbol, write a new symbol, and move left or right
State register	Stores the current state (from a finite set of states)
Transition function	Rules: given (current state, symbol read) → (new state, symbol to write, direction to move)
Start state	The initial state
Halt state(s)	States that stop the machine (accept/reject)

How a Turing Machine Works

At each step:

1. Read the symbol under the head

2. Look up the transition rule for (current state, current symbol)

3. Write the specified symbol

4. Move the head left (L) or right (R)

5. Change to the new state

6. If the new state is a halt state, stop. Otherwise, repeat.

Transition Table Example

A TM that adds 1 to a binary number (written on the tape with the least significant bit under the head):

State	Read	Write	Move	Next State
q0	0	1	R	qhalt
q0	1	0	L	q0
q0	B	1	R	qhalt

Trace on input "11" (binary 3, expecting binary 4 = "100"):

• Start: tape = ...B11B..., state q0. Read 1 → write 0, move L, stay q0
• Tape = ...B01B... wait — we need to read from least significant bit. Let's say head starts at rightmost 1.
• ...B11B..., q0: Read 1, write 0, move L → ...B10B..., q0
• Read 1, write 0, move L → ...B00B..., q0
• Read B, write 1, move R → ...100B..., qhalt
• Result: "100" = 4 ✓

The Church-Turing Thesis

"Any function that can be computed by an effective procedure can be computed by a Turing machine."

This is a thesis (a claim), not a theorem — it cannot be formally proved because "effective procedure" is an informal concept. However, every proposed model of computation (lambda calculus, recursive functions, register machines, modern programming languages) has been shown to be equivalent to a Turing machine.

Implication: If a problem cannot be solved by a Turing machine, it cannot be solved by any computer, no matter how powerful.

Universal Turing Machine (UTM)

A Universal Turing Machine is a Turing machine that can simulate any other Turing machine. It takes as input:

1. A description (encoding) of the TM to simulate

2. The input for that TM

It then simulates the described TM on the given input, producing the same result.

Significance: The UTM is the theoretical basis for the stored-program computer (von Neumann architecture). Just as a UTM can run any TM, a modern computer can run any program — the program is data.

Computability and Decidability

Term	Meaning
Computable function	A function for which a Turing machine exists that always halts with the correct output
Decidable problem	A yes/no problem for which a TM always halts with the correct answer
Undecidable problem	A yes/no problem for which NO TM can always halt with the correct answer
Recognisable (semi-decidable)	A TM exists that halts and says "yes" for yes-instances, but may loop forever on no-instances

The Halting Problem

Statement: Given a description of a Turing machine M and an input w, determine whether M will eventually halt (stop) when run on w, or run forever.

Theorem (Turing, 1936): The halting problem is undecidable. There is no algorithm that can solve it for all possible programs and inputs.

Proof (by Contradiction)

This is a beautiful and important proof:

Assume a halting oracle H(M, w) exists that always correctly returns:

• "halts" if M halts on input w
• "loops" if M loops forever on input w

Construct a new machine D that takes a machine description M as input:

D(M):
    if H(M, M) == "halts":
        loop forever
    else:
        halt

Now ask: What happens when we run D(D)?

• If D(D) halts: then H(D, D) said "halts", so D should loop forever — contradiction!
• If D(D) loops: then H(D, D) said "loops", so D should halt — contradiction!

Both cases lead to a contradiction. Therefore, H cannot exist. The halting problem is undecidable. ∎

Why the Halting Problem Matters

1. There are limits to computation: Not everything is computable, no matter how fast or powerful the computer

2. Practical implications: You cannot write a program that detects all infinite loops in other programs

3. Other undecidable problems can be proved undecidable by reducing them to the halting problem:

• Whether two programs produce the same output for all inputs
• Whether a program ever prints a specific string
• Whether a mathematical statement is provable (Gödel's incompleteness theorem is related)

Computational Complexity Classes

Class	Description	Example
P	Solvable in polynomial time	Sorting, searching
NP	Verifiable in polynomial time	Sudoku (hard to solve, easy to check)
NP-Complete	The hardest problems in NP	Travelling salesman (decision version)
NP-Hard	At least as hard as NP-Complete	Travelling salesman (optimisation)

The P vs NP question ("Is P = NP?") is one of the greatest unsolved problems in computer science and mathematics.

Exam Tips

• Be able to trace a Turing machine on a given input using a transition table
• The halting problem proof is often asked as a "describe and explain" question — practise writing it as a clear contradiction argument
• Know the Church-Turing thesis as a thesis (not a theorem) — it cannot be proved, only supported by evidence
• The Universal Turing Machine is the theoretical basis for general-purpose computers — make this connection
• Undecidable does not mean "hard" — it means impossible. No amount of computing power helps.
• Know at least one other undecidable problem besides the halting problem
• For complexity classes: P ⊆ NP, and whether P = NP is unknown