Church-Turing thesis: Worked examples — Coding deep dive

Before anything, four plain-word anchors so no symbol is unearned:

Two of the cells below name a machine-building trick we must define before we use it — otherwise the map below is meaningless:

Definition

for vs while — the only two loop shapes that matter here

A for loop counts up to a known, fixed ceiling and then stops. In the recursion language this is primitive recursion: $f (x, 0) = g (x)$ and $f (x, n + 1) = h (x, n, f (x, n))$ — you climb a ladder of height exactly $n$ . Picture a staircase with the top step already drawn: you must reach it.
A while loop searches $y = 0, 1, 2, \dots$ and stops at the first success — but nobody promised a success exists, so it may run forever. In the recursion language this is minimization, written $μ y [g (x, y) = 0]$ = "the smallest $y$ making $g$ hit zero." Picture the same staircase with no top drawn: you keep climbing until you hit a landing, which might never come.

The symbol $μ$ (Greek "mu") is just shorthand for "smallest $y$ such that…". We earn it here so the figure below can use it.

The scenario matrix

Every exam problem on CTT is really the question "which of the three boxes does this land in, and why?" Here is the full grid of case-classes this topic can hand you:

Cell	Case class	The trap it tests
A	Base / trivial function (constant, successor)	Can you show it from the ground up?
B	`for`-loop function (primitive recursive)	Bounded search ⇒ always halts
C	Fast-growing but still computable (Ackermann)	`for` loops alone miss it; need the `while` search $μ$
D	`while`-loop that may loop forever (partial)	Where partial functions come from
E	Model-swap invariance (multi-tape, quantum, RAM)	"More powerful" $=$ faster, not more computable
F	Real-world word problem (is $n$ prime?)	Use CTT to skip drawing a TM
G	Degenerate / zero input	Does the recipe survive the empty/edge case?
H	Limiting / impossible case (Halting)	CTT turns "no TM" into "no algorithm at all"
I	Exam twist (the "busy beaver"/oracle bait)	Definable ≠ computable

The nine examples below hit every cell. Each is tagged with its cell letter.

The map you are sorting into

Now that for/while (primitive recursion / $μ$ -minimization) are defined, the map is readable:

Look at the three nested regions. Everything primitive-recursive (for loops, cell B) sits inside everything reachable with the while search $μ$ (cell D), which — by the theorem — equals Turing-computable. Cell C (Ackermann) lives in the ring between B and D: computable but not for-only. Cell H (Halting) sits outside the whole picture. Keep this figure in your head; every example is a dot on it.

The examples

Worked example Example 1 — Cell A: a base function from absolute zero

Statement. Show the constant function $c (x) = 3$ is Turing-computable using only the base pieces $Z, S, P$ .

Forecast: Guess — do we need a loop at all?

Recall the base pieces: $Z (x) = 0$ (always outputs zero), $S (x) = x + 1$ (add one), $P_{1}^{1} (x) = x$ (copy the input). Why this step? These are the only "free" functions we are allowed to assume — everything else must be built.
Write $c (x) = S (S (S (Z (x))))$ . Why this step? Start at $0$ via $Z$ , then add one three times. No input-dependent looping needed, so it's a plain composition.
Composition of computable functions is computable (parent note, closure rule 1). Why? Run $Z$ , feed to $S$ , feed to $S$ , feed to $S$ — a finite fixed chain.

Verify: $c (7) = S (S (S (Z (7)))) = S (S (S (0))) = S (S (1)) = S (2) = 3.$ ✓ Constant, no loop. This is a dot deep inside region B on the figure.

Worked example Example 2 — Cell B: a

for-loop function (primitive recursive) Statement. Show multiplication $m u l t (x, n) = x \cdot n$ is primitive recursive, hence always halts. First we must build the $a dd$ it leans on — from the base pieces, no cheating.

Forecast: How many additions does computing $x \cdot 4$ take? Guess before step 4.

Build $a dd$ first. Define $a dd (x, 0) = P_{1}^{1} (x) = x$ and $a dd (x, n + 1) = S (a dd (x, n))$ . Why this step? $a dd$ is not a base primitive, so we may not assume it — we construct it by primitive recursion with $g = P_{1}^{1}$ (copy $x$ ) and $h (x, n, r) = S (r)$ (add one to the running result). This is a bounded for loop of height $n$ , so $a dd$ always halts.
Base case of $m u l t$ : $m u l t (x, 0) = 0$ , i.e. $g (x) = Z (x)$ . Why this step? Anything times zero is zero — the seed of the ladder.
Step case: $m u l t (x, n + 1) = a dd (x, m u l t (x, n))$ . Why this step? " $x$ added to itself $n + 1$ times" $=$ " $x$ added $n$ times, then one more copy of $x$ ." That is exactly the primitive-recursion shape $f (x, n + 1) = h (x, n, f (x, n))$ with $h$ built from the $a dd$ of step 1.
Because $n$ decreases to a known floor ( $0$ ), the ladder has fixed height $n$ — a bounded for loop. Why? Bounded ⇒ guaranteed to halt.

Verify: $m u l t (x, 4)$ unrolls as $a dd (x, a dd (x, a dd (x, a dd (x, 0)))) = 4 x$ , using $4$ additions. For $x = 3$ : $m u l t (3, 4) = 12.$ ✓ Region B again.

Worked example Example 3 — Cell C: fast-growing yet computable (Ackermann)

Statement. The Ackermann function $A$ grows faster than any primitive-recursive function, so it is not primitive recursive — yet it is computable. Which box? $A (0, n) = n + 1, A (m, 0) = A (m - 1, 1), A (m, n) = A (m - 1, A (m, n - 1)) .$ Each call strictly shrinks the pair $(m, n)$ in a well-ordering (lower $m$ , or same $m$ with lower $n$ ), so it always terminates.

Forecast: Total computable, partial, or uncomputable? Commit before step 3.

Every single call reduces $(m, n)$ in a decreasing order (first $m$ , then $n$ ). Why this step? A strictly decreasing chain over natural numbers cannot go forever — so every input halts.
Halts on every input $\Rightarrow$ total computable. Why? "Always finishes with an answer" is precisely the definition of total.
But its growth outpaces any bounded for-loop nesting, so no primitive-recursion scheme captures it — it needs the general recursion / while-search $μ$ machinery. Why this step? This is the whole reason $μ$ exists: to reach computable functions for loops can't. See the growth figure below.

Verify: Small check — $A (2, 2) = 7$ and $A (3, 3) = 61$ . Both finite ⇒ consistent with "always halts." ✓ This is the dot in the ring between B and D on the figure.

The blue and yellow curves are what any for-loop cost can reach; the pink Ackermann-like curve blows past both on a log scale — a visual reason a for-only scheme can never keep up, so $μ$ is genuinely needed to stay inside the computable region (cell C sits in the ring on the first figure).

Worked example Example 4 — Cell D: a

while that may run forever (partial function) Statement. Define $f (x) = μ y [g (x, y) = 0]$ where $g (x, y) = (y - x)^{2} + (x mod 2)$ . What does $f$ do, and where is the partiality? (Recall $x mod 2$ , just defined above, is $0$ for even $x$ and $1$ for odd $x$ .)

Forecast: For which inputs does $f$ answer, and for which does it loop forever?

Read $μ y [\dots]$ as "try $y = 0, 1, 2, \dots$ and stop at the first $y$ making the bracket true." Why this step? That is the definition of minimization — an unbounded while search with no promised end.
If $x$ is even, then $x mod 2 = 0$ , so $g (x, y) = (y - x)^{2}$ , which is $0$ exactly when $y = x$ . Search stops: $f (x) = x$ . Why this step? A hit exists, so the while terminates.
If $x$ is odd, then $x mod 2 = 1$ , so $g (x, y) = (y - x)^{2} + 1 \geq 1 > 0$ for all $y$ . The search never finds a zero — loops forever. Why this step? No solution ⇒ while never exits ⇒ partial.

Verify: $f (4) = 4$ (even, halts). $f (5)$ undefined (odd, loops). This is the classic partial-function signature: defined on some inputs, silent on others. ✓ A dot in region D but not in B.

Worked example Example 5 — Cell E: model-swap invariance (does a "stronger" machine compute more?)

Statement. You are handed a 3-tape nondeterministic Turing machine, then a quantum computer. Do either compute a function a plain single-tape TM cannot?

Forecast: Yes or no — and is "more powerful" about what or how fast?

Multi-tape / nondeterministic TMs are provably simulable by a single tape (parent note's robustness result). Why this step? Simulation means: same set of functions, only more steps.
A quantum computer does not hand you a clean number — its final state is a superposition, and a measurement returns outcome $y$ only with some probability $Pr [y] = ∣ α_{y} ∣^{2}$ (the squared amplitude). Why this step? This is the real gap: a quantum device is probabilistic, so "its output" is a random variable, not obviously a deterministic function.
Close the gap — but do it honestly. Restrict to a standard gate set with algebraic (or rational) amplitude entries — e.g. Hadamard, phase, CNOT, Toffoli — so every amplitude $α_{y}$ is an algebraic number produced by finitely many exact additions and multiplications. Then $α_{y}$ , and hence $Pr [y] = ∣ α_{y} ∣^{2}$ , is a computable function of the input, representable and compared exactly with algebraic-number arithmetic. Why this step? Without the algebraic-amplitude restriction an arbitrary real amplitude could be non-computable; the restriction is exactly what makes "simulate the quantum machine on a TM" a rigorous statement rather than a hand-wave. (This is why every real quantum-computing model fixes such a gate set — the Solovay–Kitaev theorem lets these gates approximate any other to any precision, so nothing is lost.)
With computable amplitudes, a single-tape TM simulates the quantum machine deterministically — enumerate all $2^{k}$ computational paths, sum their (algebraic) amplitudes exactly, and either output the most-likely $y$ or, for a bounded-error algorithm, the answer carrying probability $\geq 2/3$ . Why this step? Because the acceptance probability is computable, the classically-simulated output is a genuine deterministic Turing-computable function — the randomness is simulated, not new power.
Therefore all three models compute the same set of functions; only running time differs (the classical simulation may be exponentially slower). Why? CTT is about what is computable, not how fast — quantum pressures only the Strong/physical thesis.

Verify: Consistency check — if quantum computed a new function, the "many-models-one-class" convergence (the evidence for CTT) would collapse; it hasn't. So the answer is no new functions. ✓ Every reasonable model maps to the same region on the figure.

Worked example Example 6 — Cell F: real-world word problem (use CTT to skip the TM)

Statement. "Given an integer $n \geq 2$ , is $n$ prime?" Show it is decidable without drawing a Turing machine.

Forecast: How large a divisor do we ever need to test?

Describe a finite procedure: for $d = 2, 3, \dots, ⌊ n ⌋$ , test whether $d$ divides $n$ (i.e. whether $n mod d = 0$ ); output "composite" on the first hit, else "prime". Why this step? Any factor larger than $n$ pairs with one smaller than $n$ , so checking up to $⌊ n ⌋$ suffices.
This loop is bounded by $⌊ n ⌋$ and always halts. Why this step? Finite, mechanical, terminating — the exact profile CTT recognises.
Invoke CTT: a finite mechanical procedure $\Rightarrow$ a Turing machine exists. Why? That's the license the thesis grants — we never sketch the tape.

Verify: $n = 91$ : test $d = 2..9$ ( $⌊ 91 ⌋ = 9$ ). $91 = 7 \times 13$ , hit at $d = 7$ ⇒ composite. $n = 97$ : no divisor up to $9$ ⇒ prime. Both halt. ✓ Region B (bounded loop), a total computable predicate.

Worked example Example 7 — Cell G: the degenerate / zero-input edge

Statement. Does the primitive-recursion machinery survive at $n = 0$ , and what about a function of zero arguments (a constant)?

Forecast: Is the base case a special rule, or does it fall out naturally?

In $f (x, 0) = g (x)$ the value at $0$ is set directly by $g$ , with no recursion. Why this step? The for loop of height $n$ has height $0$ here — the loop body never runs, so we just return the seed.
A $0$ -ary function (no inputs) is just a constant; build it as in Example 1 with $S, Z$ . Why this step? "No input" is not a broken case — it's the shortest possible composition.
So the smallest input is not an exception; it is the ground floor the whole ladder stands on. Why? Every recursion must bottom out somewhere, and $0$ is that floor.

Verify: $m u l t (x, 0) = 0$ and $a dd (x, 0) = x$ — both come straight from $g$ , no loop iterations. ✓ Edge input handled, still region B.

Worked example Example 8 — Cell H: the limiting/impossible case (Halting problem)

Statement. The Halting problem — "does program $P$ on input $w$ eventually stop?" — is undecidable. Use CTT to argue no mechanical procedure of any kind (not merely: no Turing machine) solves it.

Forecast: If a clever non-Turing method solved it, would CTT survive?

Fact (proved separately, see Halting Problem): no Turing machine decides halting. Why this step? This is the diagonalization theorem — a fixed formal impossibility, established with zero reference to CTT.
State CTT precisely: every effective/mechanical procedure is computable by some Turing machine. Why this step? This is the thesis's whole content — it forbids any "recipe" from living outside the TM class.
Suppose, for contradiction, some mechanical procedure $M$ (pencil-and-paper, a robot, a hypothetical hyper-machine following clear finite rules) did decide halting. By CTT, $M$ is realisable as a Turing machine $T_{M}$ . Why this step? CTT converts the informal " $M$ is a mechanical procedure" into the formal " $T_{M}$ is a Turing machine."
Then $T_{M}$ would be a Turing machine deciding halting — contradicting step 1. So no such $M$ exists. Why? Step 1 already ruled out every TM; step 3 forced $M$ to be one, so $M$ cannot exist.
Conclusion: undecidability is universal — no algorithm, procedure, or device following finite rules decides halting, not just no TM. Why this step? That universal reach is exactly what CTT buys you: it lifts "no TM" to "no recipe anywhere."

Verify: Logical form — "no TM" ( $\neg\exists TM$ ) plus "procedure $\Rightarrow$ TM" gives "no procedure" ( $\neg\exists proc$ ) by contrapositive. Truth-table check of $(\neg t) \land (a \to t) \Rightarrow \neg a$ is a tautology. ✓ This dot sits outside every region of the figure.

Worked example Example 9 — Cell I: the exam twist ("definable ≠ computable")

Statement. The Busy Beaver function $B B (n)$ — the maximum number of steps any halting $n$ -state Turing machine runs before stopping — is perfectly well defined. Is it computable? (This is the classic "definable-but-uncomputable" / oracle-bait trap.)

Forecast: A crisp, unambiguous definition surely means computable... does it?

$B B$ is total and well-defined: for each $n$ there are only finitely many $n$ -state machines, so the maximum runtime over the halting ones is a definite finite number. Why this step? The trap is to slide from "the value exists and is unique" to "we can compute it."
Suppose $B B$ were computable. Then to test whether any given $n$ -state machine halts, run it for $B B (n) + 1$ steps: if it has not stopped by then it never will. Why this step? $B B (n)$ upper-bounds the runtime of every halting $n$ -state machine, so exceeding it certifies non-halting.
That gives a Turing machine deciding halting — impossible by Example 8. Contradiction $\Rightarrow$ $B B$ is uncomputable. Why? A computable $B B$ would smuggle in the halting-decider CTT and diagonalization jointly forbid.
Yet $B B$ is not undefined and not partial — it is a genuine total function we simply cannot compute. Why this step? This separates three ideas exams love to blur: defined (value exists), total (defined everywhere), computable (a recipe finds it). $B B$ is the first two but not the third.

Verify: Known small values $B B (1) = 1, B B (2) = 6$ exist and are finite (so $B B$ is well-defined) yet the function as a whole is uncomputable. "Well-defined but uncomputable" — the exact exam gotcha. ✓ Outside the figure, like cell H.

Recall Rapid-fire self-test over the whole matrix

Which cell is each in? Answer before revealing. $c (x) = 3$ ::: Cell A — base composition, region B, total. $m u l t (x, n)$ ::: Cell B — primitive recursive, always halts. Ackermann $A (m, n)$ ::: Cell C — total computable but NOT primitive recursive. $μ y [(y - x)^{2} + (x mod 2) = 0]$ ::: Cell D — partial (loops on odd $x$ ). A quantum computer's output function ::: Cell E — same set as a plain TM, only faster. "Is $n$ prime?" ::: Cell F — bounded loop, decidable, invoke CTT. Value of $m u l t (x, 0)$ ::: Cell G — $0$ , the degenerate base, no loop runs. Halting problem ::: Cell H — undecidable; CTT makes it universal. Busy Beaver $B B (n)$ ::: Cell I — well-defined yet uncomputable.

See also: Turing Machine, Lambda Calculus, Mu-Recursive Functions, Halting Problem, Decidability and Recursive Languages, Universal Turing Machine, Computational Complexity, P vs NP.