Foundations of mathematics

Recursive functions and Turing machines

Formal models that define exactly which functions can be computed by an algorithm.

IntuitionWhat can a machine compute?

A calculator can add and multiply; a compiler can check types; an AI can (sometimes) answer questions. But is there a function that no algorithm, however clever, can ever compute? Alan Turing's answer — yes — came from a precise mathematical model of "algorithm": the Turing machine, a tape, a read/write head, and a finite table of rules. Two seemingly different formalizations, recursive functions (built from simple pieces by composition and recursion) and Turing machines (a mechanical step-by-step process), turn out to compute exactly the same class of functions — strong evidence for the Church–Turing thesis that this really is "everything computable".

State-transition graph of a small Turing machine: nodes are states, edges are transitions labeled by (read symbol → write symbol, move).

UndergraduatePrimitive recursive and $\mu$ -recursive functions

Definition: Primitive recursive functions

The primitive recursive functions are the smallest class of functions $\mathbb N^k \to \mathbb N$ containing the zero function, the successor $S(n)=n+1$ , and all projections, and closed under composition and primitive recursion: given $g:\mathbb N^k\to\mathbb N$ and $h:\mathbb N^{k+2}\to\mathbb N$ , the recursion $f(\vec x,0)=g(\vec x)$ , $f(\vec x,n+1)=h(\vec x,n,f(\vec x,n))$ defines a new primitive recursive $f$ . Addition, multiplication, exponentiation, and every "for-loop" program with a fixed bound are all primitive recursive — and every primitive recursive function is total (defined on all inputs) and halts on a bounded number of steps for each input.

f(\vec x,0)=g(\vec x), \qquad f(\vec x,n+1)=h(\vec x,n,f(\vec x,n))

To capture all computable functions — including ones that might not halt — we add one more operator. The ** $\mu$ -recursive (general recursive) functions add unbounded minimization**: $\mu y.\,[P(\vec x,y)=0]$ returns the least $y$ such that $P(\vec x,y)=0$ , searching $y=0,1,2,\dots$ — and simply never returns if no such $y$ exists. This is exactly what makes $\mu$ -recursive functions capable of not halting, and Kleene's theorem shows they compute exactly the same class of (partial) functions as Turing machines.

\mu y.\,[P(\vec x,y)=0] = \min\{y : P(\vec x,y)=0\}

Primitive recursive vs. general ( $\mu$ -)recursive vs. Turing-computable
Class	Built from	Always halts?	Example
Primitive recursive	Composition + bounded recursion	Yes, always total	$+,\times,$ exponentiation
General ( $\mu$ -)recursive	Primitive recursion + unbounded $\mu$	No, may loop forever	Ackermann function $A$
Turing-computable (partial)	State + tape + transition rules	No, equals $\mu$ -recursive exactly	Any algorithm whatsoever

Theorem: Undecidability of the Halting Problem

There is no algorithm $H(e,x)$ that, for every program index $e$ and input $x$ , always halts and correctly outputs whether $\varphi_e(x)$ (running program $e$ on input $x$ ) halts.

Why is it true?

This is the mathematical reason why no antivirus, compiler, or IDE can ever perfectly detect infinite loops, dead code, or "this function always crashes" in full generality — not a limitation of today's engineering, but a hard mathematical wall.

Proof

Suppose, for contradiction, that such a decider $H$ exists: $H(e,x)=1$ if $\varphi_e(x)\!\downarrow$ (halts) and $H(e,x)=0$ if $\varphi_e(x)\!\uparrow$ (runs forever), and $H$ itself always halts with the correct answer.

Using $H$ , build a new program $D$ that, on input $e$ : computes $H(e,e)$ ; if $H(e,e)=1$ , then $D$ enters an infinite loop; if $H(e,e)=0$ , then $D$ halts immediately. $D$ is built effectively from $H$ (just $H$ plus an if-statement and a loop), so it has some program index $d$ , i.e. $D=\varphi_d$ .

Now ask the self-referential question: does $\varphi_d(d)$ halt?

Case 1: if $\varphi_d(d)$ halts, then by correctness of $H$ , $H(d,d)=1$ . But by the definition of $D$ , $H(d,d)=1$ makes $D$ loop forever on input $d$ — i.e. $\varphi_d(d)$ does not halt. Contradiction.

Case 2: if $\varphi_d(d)$ does not halt, then by correctness of $H$ , $H(d,d)=0$ . But by the definition of $D$ , $H(d,d)=0$ makes $D$ halt on input $d$ — i.e. $\varphi_d(d)$ does halt. Contradiction.

Both cases are contradictory, so the assumption that $H$ exists is false. The Halting Problem is undecidable. $\blacksquare$

AdvancedRice's theorem

The Halting Problem is just one example of a much broader phenomenon. Call a property $P$ of partial computable functions semantic if it depends only on the function $\varphi_e$ computed by program $e$ , not on the source code itself, and nontrivial if some computable function has it and some does not.

Theorem: Rice's theorem

For every nontrivial semantic property $P$ of partial computable functions, the set $\{e : \varphi_e \text{ has property } P\}$ is undecidable.

Why is it true?

This single theorem instantly rules out algorithms for "does this program compute the zero function", "does this program compute a total function", "are these two programs equivalent", and countless other natural questions about program behavior — all in one stroke, without a separate diagonal argument for each.

Proof

WLOG assume the everywhere-undefined function $\emptyset$ (computed by a program that never halts on any input) does not have property $P$ — otherwise argue with the complement property $\lnot P$ , which is decidable exactly when $P$ is. Since $P$ is nontrivial, fix some program $e_0$ whose function $\varphi_{e_0}$ does have property $P$ .

Suppose, for contradiction, that $P$ is decidable by some algorithm $D$ (given a program index, $D$ halts and correctly reports whether that program's function has property $P$ ). We reduce the Halting Problem to $P$ , contradicting Theorem 1.

Given any pair $(e,x)$ , effectively construct (by simple textual manipulation — Kleene's s-m-n theorem) a new program $e'$ that, on any input $y$ : first simulates program $e$ running on input $x$ ; if that simulation ever halts, then $e'$ goes on to simulate program $e_0$ on input $y$ and outputs whatever it outputs.

Now examine the two possibilities. If $e$ halts on $x$ : the simulation of $e$ on $x$ finishes, so $e'$ then behaves exactly like $e_0$ on every input, i.e. $\varphi_{e'}=\varphi_{e_0}$ — which has property $P$ (since $P$ is semantic, it only depends on the function computed, and $\varphi_{e_0}$ has $P$ ). If $e$ does not halt on $x$ : the simulation of $e$ on $x$ never finishes, so $e'$ never reaches the $e_0$ -simulation step on any input $y$ ; hence $\varphi_{e'}$ is the everywhere-undefined function $\emptyset$ , which by assumption does not have property $P$ .

So: $e$ halts on $x$ $\iff$ $\varphi_{e'}$ has property $P$ $\iff$ $D(e')$ answers "yes". Since $(e,x)\mapsto e'$ is computable, the algorithm "compute $e'$ from $(e,x)$ , then run $D(e')$ " would decide the Halting Problem — contradicting Theorem 1. So no such $D$ exists: $P$ is undecidable. $\blacksquare$

UndergraduateReal-World Applications and Worked Examples

Compiler optimizers must decide things like "is this code reachable?" or "does this variable's value matter?" — by Rice's theorem, these are undecidable in full generality, which is exactly why real compilers use conservative approximations (they may keep some genuinely dead code rather than risk deleting live code). The Busy Beaver function $BB(n)$ — the largest number of steps an $n$ -state halting Turing machine can take before stopping — is a concrete, uncomputable function: known values are $BB(1)=1$ , $BB(2)=6$ , $BB(3)=21$ , $BB(4)=107$ , and in 2024 the collaborative Busy Beaver Challenge (led by Tristan Stérin and collaborators, with a Coq-verified proof from a contributor using the pseudonym "mxdys") established $BB(5)=47{,}176{,}870$ — showing that even this "simple" combinatorial question is only computable case-by-case, never by a general algorithm.

Example: Unfolding the Ackermann function $A(2,2)$

Using the rules $A(0,n)=n+1$ , $A(m,0)=A(m-1,1)$ for $m>0$ , and $A(m,n)=A(m-1,A(m,n-1))$ for $m,n>0$ , compute $A(2,2)$ step by step, and explain why the Ackermann function is total but not primitive recursive.

Solution

$A(2,2)=A(1,A(2,1))$ by the third rule. We first need $A(2,1)=A(1,A(2,0))$ , and $A(2,0)=A(1,1)$ by the second rule.

$A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3$ (unfolding twice with the second and first rules). So $A(2,0)=A(1,1)=3$ , hence $A(2,1)=A(1,3)$ .

$A(1,3)=A(0,A(1,2))$ , and $A(1,2)=A(0,A(1,1))=A(0,3)=4$ . So $A(1,3)=A(0,4)=5$ . Hence $A(2,1)=5$ .

Back to the top: $A(2,2)=A(1,A(2,1))=A(1,5)=A(0,A(1,4))$ ; unfolding $A(1,4)=A(0,A(1,3))=A(0,5)=6$ ; so $A(1,5)=A(0,6)=7$ . So $A(2,2)=7$ .

The Ackermann function is proven total (it always eventually reduces to case $A(0,n)$ ), so it belongs to the general recursive functions — but it grows faster than every primitive recursive function (e.g. $A(3,n)=2^{n+3}-3$ , $A(4,n)$ is already a tower of exponents). Since one can show every primitive recursive function is eventually dominated by some fixed $A(k,\cdot)$ , no primitive recursive function can equal $A$ itself — a diagonal-style domination argument, not the $\mu$ -operator, is what puts Ackermann outside primitive recursion despite being total.

Example: Reducing the Halting Problem to "does this program print hello?"

Show that the problem "given a program $e$ , does running $e$ (on no input) ever print the string `hello`?" is undecidable, by a direct reduction from the Halting Problem — without invoking Rice's theorem.

Solution

Suppose, for contradiction, an algorithm $Q(e)$ decides whether running $e$ ever prints `hello`. We use $Q$ to decide the Halting Problem, contradicting Theorem 1.

Given any program $e$ and input $x$ , effectively build a new program $e'$ (no input needed) that: simulates $e$ running on $x$ ; if/when that simulation halts, $e'$ then prints `hello` and stops.

If $e$ halts on $x$ : the simulation finishes, so $e'$ reaches the print step and does print `hello`. If $e$ does not halt on $x$ : the simulation never finishes, so $e'$ never reaches the print step and never prints `hello`.

So $e$ halts on $x$ $\iff$ $Q(e')$ answers "yes". Since $(e,x)\mapsto e'$ is computable, "build $e'$ then run $Q(e')$ " decides the Halting Problem — contradicting Theorem 1. So $Q$ cannot exist: the "prints hello" problem is undecidable. (This is exactly the compiler-analysis pattern: "is this line of code ever reached" has the same shape.)

Using $A(1,n)=n+2$ , what is $A(1,3)$ ?

Which of these is a consequence of the undecidability of the Halting Problem for compiler design?

Which property is Rice's theorem NOT applicable to?

In the diagonal proof of Halting undecidability, what leads to the contradiction?

References

Wikipedia contributors (2024). Halting problem
Wikipedia contributors (2024). Rice's theorem
Wikipedia contributors (2024). Ackermann function