Church-Turing Thesis¶

From Computability, Complexity & Algorithms — Charles Brubaker and Lance Fortnow

The Thesis¶

Church-Turing Thesis: Everything computable is computable by a Turing machine.

This is a thesis, not a theorem — it cannot be formally proved since it is a claim about the physical world (what any conceivable computing device can do). It is supported by the fact that every reasonable computational model proposed so far has been shown equivalent in power to the standard Turing machine.

EquivalenceGraph — All known reasonable computational models — multitape TMs, RAM machines, modern CPUs, even quantum and probabilistic computers — are mutually equivalent in computational power.¶

Two machines are equivalent when they accept the same inputs, reject the same inputs, loop on the same inputs, and halt with matching tape contents.

Multitape Turing Machines¶

A k-tape Turing machine has \(k\) independent tapes each with its own read/write head. The transition function generalises to:

\[\delta : Q \times \Gamma^k \to Q \times \Gamma^k \times \{L, R, S\}^k\]

where \(S\) means “stay put” (head does not move).

MultitapeDiagram — A multitape Turing machine with multiple independent read/write heads.¶

StayputMachine — Simulating a stay-put \(S\) move: go left then immediately go right to stay in place.¶

Multitape machines simplify programming significantly. For example, duplicating input:

DuplicateInputComputation — A two-tape machine duplicating input separated by \(\#\) — far simpler than the single-tape equivalent.¶

SubstringSearchQuiz — *Quiz:* Design a two-tape TM for substring search.¶

Simulating Multitape on a Single Tape¶

A single-tape TM can simulate a \(k\)-tape TM by interleaving the contents of all \(k\) tapes on one tape, using dotted symbols to mark current head positions.

MultiVsSingleTapeDiagram — Single-tape encoding of a multitape configuration: tapes separated by \(\#\), dotted symbols mark head positions.¶

Simulation steps per multitape step:

Scan rightward to read all dotted (marked) symbols — find the “virtual head” on each tape.
Scan leftward, updating symbols and shifting dotted markers as needed.

MultiVsSingleTapeQuiz — *Quiz:* If the multitape TM runs in \(T(n)\) steps, what is the single-tape simulation’s running time?¶

Answer: \(O(T(n)^2)\) — each simulated step scans the entire tape of length \(O(T(n))\).

Random Access Machines (RAM)¶

The RAM model mirrors a modern CPU:

Registers \(r_0, r_1, r_2, \ldots\) storing non-negative integers.
Infinite addressable memory indexed by non-negative integers.
Instructions: read, write, load, store, add, subtract, jump, halt.
A program counter sequencing instructions.

RAMDiagram — RAM architecture: registers, memory, and instruction set resembling assembly code.¶

RAM Simulates Turing Machine¶

RAMSimTuring — Pseudocode: RAM simulating a TM. Tape cells stored in memory; state and head position in registers. Each TM step is a constant number of RAM instructions.¶

Turing Machine Simulates RAM¶

A multitape TM can simulate a RAM by dedicating tapes to:

The program (instruction sequence).
The program counter.
Each register.
The memory array (stored as index-value pairs).

TuringSimRAM — Multitape TM simulating RAM — uses one tape per register and one for memory.¶

RAMVsMultiTapeQuiz — *Quiz:* If a RAM runs in \(T(n)\) steps using values \(\leq V\), what is the multitape TM simulation overhead?¶

Answer: \(O(T(n)^2 \log V)\) — each RAM step requires scanning memory tapes, and values need \(O(\log V)\) bits to encode.

Implications¶

Since Turing machines can simulate RAMs, and RAMs resemble standard CPUs, the Church-Turing Thesis extends to:

Multi-core processors
Cloud computing clusters
Probabilistic (randomised) computers
Quantum computers
DNA computing

All of these are provably no more powerful than a single-tape Turing machine in terms of what they can compute (though they may differ in how fast they compute it).

Profound consequence: Because Turing machines cannot solve the halting problem (proved by diagonalisation), no physical computing device can solve it either — the limits of computation are absolute and device-independent.

Key Formulas¶

Multitape transition function:

\[\delta : Q \times \Gamma^k \to Q \times \Gamma^k \times \{L, R, S\}^k\]

Simulation overhead (multitape → single-tape):

\[T_\text{single}(n) = O\!\left(T_\text{multi}(n)^2\right)\]

Church-Turing Thesis (informal):

\[\text{Computable} \;\equiv\; \text{Turing-computable}\]