Visual walkthrough — Church-Turing thesis

Step 1 — What is a "function" we want to compute?

WHAT: We picture computation as a box with an input slot and an output slot.

WHY: Before asking "which functions can a machine compute?", we need a clear mental image of what a function even is. Everything later is just building fancier boxes out of simpler boxes.

PICTURE: In the figure, the amber arrow is the input number $x$ going in; the cyan arrow is the output $y$ coming out. The dashed box is the function $f$ itself — its internal rule.

Here $x$ is the input (what you feed it) and $y$ is the output (what it returns). The set $\mathbb{N}=\{0,1,2,3,\dots \}$ is just the counting numbers — our inputs and outputs live here.

Step 2 — The three starter boxes (base functions)

WHAT: We hand ourselves three trivial boxes for free.

WHY: Every construction has to start somewhere. Instead of assuming a whole computer, we start with the least controversial operations imaginable — erase to zero, count up by one, and pick one item out of a list. If a skeptic won't grant these, nothing is computable to them.

PICTURE: Reading the figure left to right — $Z$ flattens any input to $0$ (all arrows collapse to one point); $S$ shifts you one step up the number line (amber hop); $P_2^3$ reaches into a bag of three numbers and pulls out the second.

Term-by-term on $P_i^n(x_1,\dots ,x_n)=x_i$:

• $n$ = how many numbers you gave it (the size of the list),
• $i$ = which one you want back (the position, $1\le i\le n$),
• $x_i$ = the number sitting at that position — the whole output.

Step 3 — Gluing box (Composition)

WHAT: We connect boxes by pipes — the outputs of $h_1,\dots ,h_k$ become the inputs of $g$.

WHY this tool and not another: The most basic way to build a bigger procedure is "do these things, then do that thing with the results." That is exactly function composition. Without it we could never combine our three starters into anything interesting. It is finite (finitely many boxes) and always halts if each piece halts.

PICTURE: $\vec{x}$ (the arrow with the little vector-hat, meaning "a whole list of inputs at once") fans out to every $h_j$ box. Each $h_j$ produces one cyan wire. All wires plug into $g$, which emits the single final output.

Term-by-term:

• $\vec{x}$ = the shared input list, sent to all the inner boxes,
• $h_j(\vec{x})$ = the output of the $j$-th inner box (an intermediate number),
• $g(\dots )$ = the outer box that combines those intermediates into the final answer $f(\vec{x})$.

Step 4 — The for-loop box (Primitive recursion)

WHAT: We define a box that climbs a ladder: rung $0$ is set by $g$; each higher rung $n+1$ is built from the rung just below it using $h$.

WHY this tool: Composition alone can't repeat an action a variable number of times. Real algorithms loop. Primitive recursion is the bounded for loop: "starting from $n=0$, keep applying $h$ until you reach the target $n$." Because you always know the finish line in advance, this loop is guaranteed to halt.

PICTURE: Climb the amber staircase. The bottom step is $g(\vec{x})$. Each next step's height is decided by $h$, which is allowed to look at three things: the original input $\vec{x}$, the step number $n$, and the height of the step below, $f(\vec{x},n)$ (drawn as the dashed feedback arrow curling down from the previous rung).

Term-by-term on the step case $f(\vec{x},n+1)=h(\vec{x},n,f(\vec{x},n))$:

• $\vec{x}$ = the fixed extra inputs, unchanged as we climb,
• $n$ = which rung we are standing on,
• $f(\vec{x},n)$ = the value we already computed one rung down — this is the "recursion",
• $h(\dots )$ = the recipe that turns "the rung below" into "this rung".

Step 5 — The while-loop box (Minimization $\mu$)

WHAT: We add a searcher. It tries $y=0$, then $y=1$, then $y=2$, … and stops the first moment $g(\vec{x},y)$ equals $0$. That winning $y$ is the output.

WHY this tool and not the for loop: The for loop of Step 4 always knew when to stop. But many real problems are "search until you find one" with no known upper bound on how far you must look. That is the unbounded while loop. Its power and its danger: if no $y$ ever makes $g=0$, the search runs forever — the box produces nothing. This is where non-halting programs enter our clean picture.

PICTURE: Walk right along the number line testing each $y$. Green ✓ marks where $g(\vec{x},y)\ne 0$ (keep going); the amber ✗-to-✓ flag marks the first $y$ where $g$ hits $0$ — search halts there. The dashed rail running off to the right with no flag is the non-halting case.

Term-by-term on $\mu y[g(\vec{x},y)=0]$:

• $\mu y$ = "the least $y$ such that …" (the search operator),
• $g(\vec{x},y)$ = a test function; when it reads $0$ we've found our answer,
• output = that first successful $y$; if none exists, output is undefined (the machine loops).

Step 6 — The class closes, and CTT is the last brick

WHAT: We collect everything reachable from the three starters using the three glue rules. Nothing more is added.

WHY: This gives a class defined with zero mention of Turing machines — pure function-building. It is a solid, formal object we can prove theorems about. Then two facts land:

1. Theorem (provable): this class $=$ the Turing-computable functions $=$ the $\lambda$-definable functions $=$ register-machine functions. Different starting intuitions, same destination.
2. Thesis (not provable): this class also equals "everything intuitively computable" — the Church–Turing thesis itself.

PICTURE: Three independent doorways ($\mu$-recursion, Turing machines, $\lambda$-calculus) all open into the same room. The dashed amber balloon labelled "intuitively computable" is claimed — by CTT — to be that same room, but its boundary is dashed because that last equality is a belief backed by evidence, not a proof.

Step 7 — The edge case that proves the point: Halting

WHAT: We test our whole picture on a task outside the room: the Halting problem — "given a program, will it eventually stop?"

WHY this is the crucial edge case: In Step 5 we saw $\mu$-search can run forever. Deciding in advance whether such a search halts is provably impossible for any Turing machine. Feeding that through CTT turns a statement about one model ("no TM") into a statement about all possible machines ("no algorithm, ever"). That universality is CTT's real payoff — see Decidability and Recursive Languages.

PICTURE: Inside the computable room sits "is $n$ prime?" (green — a bounded search, always halts). Outside the dashed wall floats "does program $P$ halt?" (amber — no box, of any kind, can be built). The wall is exactly the reach of the three glue rules.

The one-picture summary

The whole walkthrough on one blueprint: the three starter boxes $Z,S,P$ at the bottom feed upward through composition, primitive recursion, and minimization $\mu$; that stack fills the "computable functions" room; three independent doorways (TM, $\lambda$-calculus, $\mu$-recursion) all open into it; and the dashed amber balloon "everything intuitively computable" — claimed equal by CTT — wraps the same room, with the Halting problem stranded permanently outside.

Flashcards