42.04.01 · mathematical-logic / computability-degrees

Models of Computation and the Church-Turing Thesis

shipped3 tiersLean: none

Anchor (Master): Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 1-3 and the historical notes (the equivalence of models, the Church-Turing thesis as a thesis, the universal machine and the acceptable numbering, s-m-n and the recursion theorem); Odifreddi 1989 *Classical Recursion Theory, Volume I* (North-Holland) Ch. I-II (acceptable numberings, the isomorphism theorem of Rogers, the Blum axioms separating computability from complexity); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 1-5

Intuition Beginner

Suppose you want to settle, once and for all, what counts as a "step-by-step procedure" — the kind of thing a person with unlimited paper, unlimited time, no cleverness, and no insight could carry out by blindly following rules. Cooking from a recipe, doing long division, looking a word up alphabetically: each is a finite list of instructions you apply without ever needing a flash of inspiration. The question this unit answers is what the outer boundary of that idea is. Which tasks can be done by some such procedure at all, and which can be done by none?

To make the question sharp you need a precise model of "blindly following rules." The most famous one imagines a long paper tape divided into cells, a reading head that sits over one cell, and a tiny rulebook. The head looks at the symbol under it, checks its current mood (one of finitely many internal states), and the rulebook tells it: write this symbol, move one cell left or right, switch to that mood. Nothing else. That austere device is a Turing machine, and the surprising claim is that anything you could compute with any honest procedure, you could compute with one of these.

The strangeness is that there are many other ways to pin down "procedure" — building number-functions from a few starter pieces, a machine with counters instead of a tape, even a calculus of pure substitution. They look nothing alike. Yet they all carve out exactly the same collection of computable tasks. When that many independent attempts agree, you start to believe the boundary is real and not an artifact of one design.

What you carry forward: there is a robust line between the computable and the not-computable, the same line no matter which honest model you pick, and the belief that this line captures the everyday notion of "doable by a procedure" is the Church-Turing thesis.

Visual Beginner

A Turing machine is a head over a tape plus a rulebook. Below, a machine that adds one to a number written in tally marks runs for a few steps. The tape holds marks (here 1) and blanks (_); the head position is shown by the caret.

   rulebook (state q reads symbol -> write, move, new state):
     q0 reads 1  ->  write 1, move Right, stay q0   (scan past the marks)
     q0 reads _  ->  write 1, move Right, halt       (append one mark, stop)

   start:   _ 1 1 1 _ _        state q0
              ^
   step 1:  _ 1 1 1 _ _        state q0   (read 1, move right)
                ^
   step 2:  _ 1 1 1 _ _        state q0
                  ^
   step 3:  _ 1 1 1 _ _        state q0
                    ^
   step 4:  _ 1 1 1 1 _        HALT       (read _, wrote 1, stop)
                      ^
   input  = three marks (the number 3)
   output = four marks   (the number 4)

Read it top to bottom. The head starts on the leftmost mark in state q0. Each time it reads a mark it leaves it alone and steps right, staying in q0. When it finally reads a blank it writes one new mark and halts. Three marks became four: the machine computed "add one."

step	symbol read	action	result
1	`1`	write `1`, move right	head over 2nd mark
2	`1`	write `1`, move right	head over 3rd mark
3	`1`	write `1`, move right	head over blank
4	`_`	write `1`, halt	a 4th mark appears

The whole "program" is the two-line rulebook. Everything a Turing machine ever does is a rulebook this plain, run long enough.

Worked example Beginner

We build the function "double a number" out of starter pieces, the second great model, and watch it agree with a machine. The starter pieces are: the constant zero, the "add one" operation (call it $S$ for successor), and the rule that lets you define a function by saying what it does at zero and how it grows by one step at a time. That last rule is recursion: to define $f$ you give $f (0)$ and a way to get $f (n + 1)$ from $f (n)$ .

Step 1. Define doubling $d$ by recursion. Set $d (0) = 0$ . Set $d (n + 1) = S (S (d (n)))$ — that is, double of $n + 1$ is two more than double of $n$ .

Step 2. Unfold it at $n = 3$ . We need $d (3)$ , so first $d (0), d (1), d (2)$ .

Step 3. Compute upward. $d (0) = 0$ . Then $d (1) = S (S (d (0))) = S (S (0)) = 2$ . Then $d (2) = S (S (d (1))) = S (S (2)) = 4$ . Then $d (3) = S (S (d (2))) = S (S (4)) = 6$ .

Step 4. Check against a machine. A Turing machine that copies every mark once (reads a mark, goes to the far end, writes a mark, comes back) turns three marks into six. Same answer, $6$ .

What this tells us: two models that share no parts — a tape device and a recipe built from zero, successor, and recursion — computed the very same function. The next sections make "built from these pieces" and "computed by a machine" precise, and state why every honest model lands on the same class of functions.

Check your understanding Beginner

Formal definition Intermediate+

A Turing machine is a tuple $M = (Q, Σ, δ, q_{0}, B, F)$ with $Q$ a finite set of states, $Σ$ a finite tape alphabet containing a distinguished blank $B$ , an input alphabet $Σ_{0} \subseteq Σ ∖ {B}$ , an initial state $q_{0} \in Q$ , a set $F \subseteq Q$ of halting states, and a partial transition function $δ : (Q ∖ F) \times Σ \to Q \times Σ \times {L, R}$ . A configuration records the tape contents (a function $Z \to Σ$ equal to $B$ off a finite set), the head position, and the state. The one-step relation $⊢_{M}$ rewrites a configuration by applying $δ$ to the (state, scanned symbol) pair: write the new symbol, move the head one cell $L$ or $R$ , enter the new state. A computation on input $w$ is the (finite or infinite) sequence of configurations starting from $q_{0}$ on $w$ surrounded by blanks; $M$ halts on $w$ if the sequence reaches a state in $F$ ^{[Soare Ch. 1]}.

A partial function $ψ : N^{k} \to N$ is Turing-computable if some $M$ , started with $\overset{n}{ˉ} = (n_{1}, \dots, n_{k})$ encoded on its tape, halts with $ψ (\overset{n}{ˉ})$ encoded as output exactly when $ψ (\overset{n}{ˉ})$ is defined, and fails to halt when $ψ (\overset{n}{ˉ})$ is undefined. A total such $ψ$ is computable. A set $A \subseteq N$ is computable (decidable) if its characteristic function $χ_{A}$ is computable; it is computably enumerable (c.e.) if it is the domain of some partial computable function, equivalently the range of a computable function or the empty set.

The partial recursive functions are generated from the basic functions — the zero function $Z (n) = 0$ , the successor $S (n) = n + 1$ , the projections $P_{i}^{k} (\overset{n}{ˉ}) = n_{i}$ — by three operations: composition, primitive recursion (define $f (\overset{n}{ˉ}, 0) = g (\overset{n}{ˉ})$ and $f (\overset{n}{ˉ}, m + 1) = h (\overset{n}{ˉ}, m, f (\overset{n}{ˉ}, m))$ ), and the $μ$ -operator (minimisation: $μ m [R (\overset{n}{ˉ}, m)]$ is the least $m$ with $R (\overset{n}{ˉ}, m)$ true and all smaller values defined, undefined if no such $m$ ). The functions built without $μ$ are the primitive recursive functions, all total; $μ$ is what introduces partiality and non-termination. Register (counter) machines, $λ$ -calculus, and while-programs each generate a class of partial functions by their own operational semantics. The basic theorem, stated next, is that all of these classes coincide.

Counterexamples to common slips Intermediate+

"A computable function must be total — it always returns a value." Partial computable functions are central, not pathological: the $μ$ -operator and unbounded loops produce functions undefined on some inputs (the machine runs forever there). Restricting to total functions loses the enumeration ${φ_{e}}$ , since "is $φ_{e}$ total?" is itself undecidable.
"Computable and computably enumerable are the same." A set is computable iff both it and its complement are c.e. (Post). The halting set is c.e. but not computable; its complement is not even c.e. The c.e. sets are the projections of computable relations, a strictly larger class than the decidable sets.
"Primitive recursive equals computable." Every primitive recursive function is computable and total, but the Ackermann function is computable, total, and not primitive recursive. Minimisation genuinely enlarges the class, and it is exactly the source of both the extra total functions and all the partial ones.
"The Church-Turing thesis is a theorem about Turing machines." The equivalence of Turing machines with the partial recursive functions is a theorem. The thesis is the further identification of that mathematically fixed class with the informal notion of effective calculability; the informal side cannot enter a proof.

Key theorem with proof Intermediate+

The signature result is the existence of a universal machine and the s-m-n theorem, which together turn programs into data and data into programs. Fix a computable bijective Gödel numbering of Turing machines, so machine $e$ computes the partial function $φ_{e}$ , and let ${φ_{e}}_{e \in N}$ enumerate all unary partial computable functions.

Theorem (universal function and s-m-n). (i) There is a partial computable function $U$ of two arguments — equivalently a single universal Turing machine — with $U (e, x) = φ_{e} (x)$ for all $e, x$ (with both sides simultaneously defined or undefined). (ii) For all $m, n \geq 1$ there is a primitive recursive injection $s_{n}^{m} : N^{m + 1} \to N$ with $$ \varphi^{(n)}_{s^m_n(e, \bar y)}(\bar x) = \varphi^{(m+n)}_e(\bar y, \bar x) $$ for all $e$ , all parameter tuples $\overset{y}{ˉ} \in N^{m}$ , and all $\overset{x}{ˉ} \in N^{n}$ .

Proof. (i) A universal machine $U$ is given an index $e$ and an input $x$ . It decodes $e$ into the finite transition table $δ_{e}$ of machine $e$ — possible because the numbering is computable, so the lookup "what does machine $e$ do in state $q$ reading symbol $a$ ?" is a computable function of $(e, q, a)$ . $U$ then maintains, on its own tape, an encoding of a configuration of machine $e$ : the simulated tape contents, head position, and state. At each round $U$ reads off the simulated scanned symbol, consults $δ_{e}$ , and rewrites the encoded configuration accordingly. $U$ halts exactly when the simulated machine enters a halting state, leaving $φ_{e} (x)$ encoded as output; if machine $e$ runs forever on $x$ , so does $U$ . Hence $U (e, x) = φ_{e} (x)$ with matching domains.

(ii) Fix $m, n$ and the parameters $\overset{y}{ˉ}$ . Given an index $e$ for an $(m + n)$ -ary function, define a new machine $M_{e, \overset{y}{ˉ}}$ that, on input $\overset{x}{ˉ}$ , first writes the fixed constants $\overset{y}{ˉ}$ onto the tape in the first $m$ argument positions, shifts $\overset{x}{ˉ}$ into the remaining positions, and then runs machine $e$ . Each step of this construction — prepending fixed constants, shifting input, and concatenating the transition table of $e$ — is a uniform editing operation on the Gödel code of $e$ , hence a primitive recursive function of $e$ and $\overset{y}{ˉ}$ ; let $s_{n}^{m} (e, \overset{y}{ˉ})$ be the resulting index. By construction $M_{e, \overset{y}{ˉ}}$ on input $\overset{x}{ˉ}$ behaves as machine $e$ on $(\overset{y}{ˉ}, \overset{x}{ˉ})$ , so $φ_{s_{n}^{m} (e, \overset{y}{ˉ})} (\overset{x}{ˉ}) = φ_{e} (\overset{y}{ˉ}, \overset{x}{ˉ})$ . The editing distinct codes never collide, so $s_{n}^{m}$ may be taken injective. $□$

Bridge. This theorem is the foundational reason a fixed numbering of programs behaves like a programming language: the universal function $U$ is an interpreter, and $s_{n}^{m}$ is exactly partial evaluation — freezing some inputs of a program to produce, computably and uniformly, the index of the specialised program. This is exactly the mechanism by which computability theory treats indices as first-class data, and it generalises the everyday move of currying a function. The pair builds toward the recursion (fixed-point) theorem, where s-m-n supplies the self-reference, and it appears again in the halting problem 42.04.02, where $U$ lets a single machine simulate all others so that diagonalising against ${φ_{e}}$ produces an undecidable set. The central insight is that "program" and "input" are interchangeable once both are natural numbers; putting these together, the universal machine plus s-m-n is what makes the enumeration ${φ_{e}}$ an acceptable numbering, the structure every later construction in the chapter silently uses.

Exercises Intermediate+

Exercise 3 (medium, symbolic).

Prove the padding lemma: there is a primitive recursive injection $pad : N^{2} \to N$ such that for all $e, i$ , $φ_{pad (e, i)} = φ_{e}$ , and $i \mapsto pad (e, i)$ is injective. Conclude every partial computable function has infinitely many indices.

Hint

Adjoin $i$ unreachable "dead" states to machine $e$ , or append redundant instructions; this changes the code but not the computed function.

Answer

Given $e$ , decode its transition table and append $i$ fresh states $r_{1}, \dots, r_{i}$ that are never reachable from $q_{0}$ (assign them arbitrary transitions, e.g. self-loops; since no rule ever enters them they affect no computation). Re-encode the enlarged machine; call the index $pad (e, i)$ . Editing a Gödel code by appending a prescribed number of inert states is a uniform, primitive recursive operation. The computed function is unchanged because the reachable part of the machine is identical, so $φ_{pad (e, i)} = φ_{e}$ . Distinct $i$ yield machines with distinct state counts, hence distinct codes, so $i \mapsto pad (e, i)$ is injective and ${pad (e, i) : i \in N}$ is an infinite set of indices for $φ_{e}$ . Rubric: full credit for an explicit padding construction, the primitive recursiveness of the code edit, invariance of the computed function, and the injectivity giving infinitely many indices.

Exercise 4 (medium, symbolic).

Show that a set $A$ is computable if and only if both $A$ and its complement $\overline{A}$ are computably enumerable.

Hint

For the hard direction, run enumerations of $A$ and $\overline{A}$ in parallel ("dovetail") and wait for $n$ to appear in one of them.

Answer

( $\Rightarrow$ ) If $A$ is computable then $χ_{A}$ is computable, so $A$ is the domain of the partial function that halts when $χ_{A} = 1$ and diverges otherwise, hence c.e.; the same applies to $\overline{A}$ using $χ_{\overline{A}} = 1 - χ_{A}$ . ( $\Leftarrow$ ) Suppose $A = dom (φ_{a})$ and $\overline{A} = dom (φ_{b})$ . To decide $n \in A$ , dovetail the computations $φ_{a} (n)$ and $φ_{b} (n)$ : run them in interleaved steps until one halts. Exactly one does, since $n$ lies in $A$ or in $\overline{A}$ . If $φ_{a} (n)$ halts first, output $1$ ; if $φ_{b} (n)$ , output $0$ . This is a total computable procedure, so $χ_{A}$ is computable and $A$ is decidable. Rubric: full credit for both directions, with the dovetailing argument and the appeal to $n \in A \cup \overline{A}$ guaranteeing halting.

Exercise 6 (hard, symbolic).

Using the universal function and s-m-n, prove there is a total computable $g$ with $φ_{g (e)} (x) = φ_{e} (φ_{e} (x))$ for all $e, x$ (composition of a machine with itself, uniformly in its index).

Hint

The two-argument function $(e, x) \mapsto U (e, U (e, x))$ is partial computable; apply s-m-n to its index in the variable $e$ .

Answer

Define $θ (e, x) = U (e, U (e, x))$ , where $U$ is the universal function. Since $U$ is partial computable and composition of partial computable functions is partial computable, $θ$ is partial computable; let $c$ be an index, so $φ_{c}^{(2)} (e, x) = θ (e, x) = φ_{e} (φ_{e} (x))$ , with the convention that the outer application is undefined whenever the inner $φ_{e} (x)$ is. By the s-m-n theorem there is a primitive recursive $g (e) := s_{1}^{1} (c, e)$ with $φ_{g (e)} (x) = φ_{c}^{(2)} (e, x) = φ_{e} (φ_{e} (x))$ . The function $g$ is primitive recursive, hence total computable, as required. Rubric: full credit for forming the partial computable two-argument function, naming an index, and applying s-m-n in the parameter $e$ to obtain a total $g$ .

Exercise 7 (hard, symbolic).

Prove that the equivalence of two models — Turing machines and the partial recursive functions — gives, in one direction, that every partial recursive function is Turing-computable, by induction on its construction.

Hint

Build machines for the basic functions, then machines implementing composition, primitive recursion, and $μ$ , using that Turing-computable functions are closed under each.

Answer

Induct on the generation of the partial recursive function $ψ$ . Base: $Z$ , $S$ , and each $P_{i}^{k}$ are computed by simple machines (erase to a single blank; append one mark; select the $i$ -th argument block). Closure under composition: given machines for $h$ and $g_{1}, \dots, g_{r}$ , a machine for $h (g_{1}, \dots, g_{r})$ runs each $g_{j}$ on a copy of the input, collects the outputs, then runs $h$ ; this halts iff every sub-computation does, matching the domain of the composite. Closure under primitive recursion: given machines for $g$ and $h$ , compute $f (\overset{n}{ˉ}, m)$ by setting $f (\overset{n}{ˉ}, 0) = g (\overset{n}{ˉ})$ and iterating $h$ exactly $m$ times, a bounded loop a machine can run. Closure under $μ$ : to compute $μ m [R (\overset{n}{ˉ}, m) = 0]$ , test $R (\overset{n}{ˉ}, 0), R (\overset{n}{ˉ}, 1), \dots$ in turn, halting at the first value $0$ ; this halts exactly when such an $m$ exists and all earlier tests halt, reproducing the partiality of $μ$ . Each closure is a finite machine-assembly, so by induction every partial recursive $ψ$ is Turing-computable. Rubric: full credit for the base machines and the three closure constructions with correct domain (halting) behaviour, especially the divergence of the $μ$ -loop.

Advanced results Master

The universal function and s-m-n are not features of one numbering but the defining structure of an acceptable numbering, and the theorems below show how rigid that structure is, how it produces self-reference, and where it stops — at the boundary with complexity.

Theorem 1 (acceptable numberings; Rogers' isomorphism theorem). Call a numbering $ν : N \to (N ⇀ N)$ of the unary partial computable functions acceptable if it admits a universal function and satisfies the s-m-n theorem. Any two acceptable numberings $ν, ν^{'}$ are computably isomorphic: there is a computable bijection $π : N \to N$ with $ν^{'} = ν \circ π$ ^{[Odifreddi Ch. II]}. Thus the standard ${φ_{e}}$ is canonical up to a computable permutation of indices; no theorem of the subject depends on the particular Gödel coding chosen, only on acceptability. The proof builds $π$ by a back-and-forth construction, at each stage extending a partial computable injection using s-m-n to translate indices each way and the padding lemma to supply fresh targets, exactly as Myhill's theorem builds a computable bijection between two one-one-equivalent sets.

Theorem 2 (the recursion / fixed-point theorem). For every total computable $f$ there is an index $n$ — a fixed point — with $φ_{n} = φ_{f (n)}$ ^{[Rogers Ch. 11]}. The proof is a diagonal use of s-m-n: from the partial computable $(x, y) \mapsto φ_{f (s_{1}^{1} (x, x))} (y)$ obtain an index $v$ , then $n = s_{1}^{1} (v, v)$ satisfies $φ_{n} = φ_{f (n)}$ . The theorem licenses programs that refer to their own index, the precise sense in which "a program may use its own source code" is legitimate, and it is the engine behind Kleene's normal form and many undecidability proofs, including the index-set form of Rice's theorem.

Theorem 3 (Kleene normal form). There is a primitive recursive predicate $T (e, x, c)$ — " $c$ codes a halting computation of machine $e$ on input $x$ " — and a primitive recursive output extractor $U_{out}$ such that $$ \varphi_e(x) \simeq U_{\mathrm{out}}\bigl(\mu c,[,T(e, x, c),]\bigr). $$ Every partial computable function is therefore a single application of $μ$ to a primitive recursive predicate: one unbounded search suffices ^{[Soare Ch. 2]}. The predicate $T$ is decidable because checking that $c$ is a valid, terminating computation history is a bounded verification, and this is the exact technical sense in which "running a program for a witnessed finite number of steps" is computable while "deciding whether it ever halts" is not.

Theorem 4 (the Blum axioms; computability is not complexity). A complexity measure is a family ${Φ_{e}}$ (e.g. number of steps of machine $e$ ) satisfying Blum's two axioms: $Φ_{e} (x)$ is defined iff $φ_{e} (x)$ is, and the predicate $Φ_{e} (x) = m$ is computable ^{[Odifreddi Ch. II]}. Every reasonable resource — time, space — is such a measure, and the speed-up and gap theorems show the measures behave wildly (some functions admit no best program). The point for this unit is structural: the bare notion of computability fixed by the equivalent models says nothing about cost. Resource-bounded computation — the polynomial-time class, $P$ versus $NP$ , the big-O calculus — is an additional layer built on top of an already-fixed model, and it is the subject of 25.03.01, not of the computability theory developed here.

Synthesis. The acceptable numbering is the central insight that organises the entire chapter: the universal function makes one machine simulate all machines, s-m-n makes specialisation computable, and together — by Theorem 1 — they pin the numbering down to a computable permutation, so every later result is independent of the coding. This is exactly why the recursion theorem holds in every acceptable numbering and why diagonalisation against ${φ_{e}}$ is well defined: the fixed-point construction is nothing but s-m-n applied to itself, and it generalises the self-reference of Gödel's incompleteness sentences 42.01.09 pending into a tool that works for arbitrary program transformations. The Kleene normal form is dual to the universal function — one compresses all computation into a single $μ$ over a decidable predicate, the other expands an index back into a running simulation — and putting these together gives the c.e. sets as exactly the $Σ_{1}$ projections that seed the arithmetical hierarchy 42.04.05. The bridge from this fixed model to its undecidable consequences is the halting problem 42.04.02, where $U$ supplies the self-application that diagonalisation needs; and the bridge away from it, into resource theory, is the Blum axioms, which show that complexity is structure added on top of computability, the foundational reason the big-O world of 25.03.01 is a genuinely separate subject rather than a refinement internal to this one.

Full proof set Master

Proposition 1 (universal partial computable function exists). There is a partial computable $U$ with $U (e, x) ≃ φ_{e} (x)$ for all $e, x$ .

Proof. By Kleene normal form (Theorem 3) there is a primitive recursive predicate $T (e, x, c)$ and a primitive recursive $U_{out}$ with $φ_{e} (x) ≃ U_{out} (μ c [T (e, x, c)])$ . Define $U (e, x) := U_{out} (μ c [T (e, x, c)])$ . The right side is built from a primitive recursive predicate by one application of $μ$ followed by a primitive recursive function, hence partial recursive in the pair $(e, x)$ , hence partial computable. For each fixed $e, x$ the search terminates iff machine $e$ halts on $x$ , and then returns its output, so $U (e, x) ≃ φ_{e} (x)$ with matching domains. $□$

Proposition 2 (s-m-n). For each $m, n$ there is a primitive recursive $s_{n}^{m}$ with $φ_{s_{n}^{m} (e, \overset{y}{ˉ})}^{(n)} (\overset{x}{ˉ}) ≃ φ_{e}^{(m + n)} (\overset{y}{ˉ}, \overset{x}{ˉ})$ .

Proof. Define an effective code transformation that, from $e$ and constants $\overset{y}{ˉ}$ , produces the index of the machine which writes $\overset{y}{ˉ}$ into the first $m$ argument slots and then runs machine $e$ . Concretely, on the Gödel code of $e$ prepend a fixed initial segment of states that print the numerals $\overset{y}{ˉ}$ and reposition the head, then splice in $e$ 's transition table with states renamed by a fixed offset. Each operation is a primitive recursive function of $(e, \overset{y}{ˉ})$ since it is a bounded edit of finite code; let $s_{n}^{m} (e, \overset{y}{ˉ})$ be the result. By construction the new machine on $\overset{x}{ˉ}$ simulates $e$ on $(\overset{y}{ˉ}, \overset{x}{ˉ})$ , giving the stated identity with matching domains. Choosing the offset to encode $\overset{y}{ˉ}$ faithfully makes $s_{n}^{m}$ injective. $□$

Proposition 3 (recursion theorem). Every total computable $f$ has a fixed point $n$ with $φ_{n} = φ_{f (n)}$ .

Proof. Consider the partial computable function $ψ (x, y) ≃ φ_{f (s_{1}^{1} (x, x))} (y)$ , well defined since $s_{1}^{1}$ is total computable, $f$ is total computable, and $U$ supplies $φ_{(\cdot)} (\cdot)$ . Let $v$ be an index with $φ_{v}^{(2)} = ψ$ , and set $n := s_{1}^{1} (v, v)$ . Then for all $y$ , $$ \varphi_n(y) = \varphi_{s^1_1(v,v)}(y) \simeq \varphi^{(2)}v(v, y) = \psi(v, y) \simeq \varphi{f(s^1_1(v,v))}(y) = \varphi_{f(n)}(y), $$ using s-m-n at the first and the definition of $ψ$ at the last step. Hence $φ_{n} = φ_{f (n)}$ . $□$

Proposition 4 (the halting set is c.e. but not computable — preview of 42.04.02). The set $K = {e : φ_{e} (e) ↓}$ is computably enumerable and not computable.

Proof. $K$ is the domain of the partial computable function $e \mapsto U (e, e)$ , hence c.e. If $K$ were computable, then $g$ defined by $g (e) = φ_{e} (e) + 1$ if $e \in K$ and $g (e) = 0$ otherwise would be total computable, with index $e_{0}$ , so $g = φ_{e_{0}}$ . Evaluate at $e_{0}$ : if $e_{0} \in K$ then $g (e_{0}) = φ_{e_{0}} (e_{0}) + 1 = g (e_{0}) + 1$ , impossible; if $e_{0} \in / K$ then $φ_{e_{0}} (e_{0}) ↑$ , yet $g (e_{0}) = 0$ is defined, so $φ_{e_{0}} (e_{0}) ↓$ , contradiction. Hence $K$ is not computable. The argument is the diagonalisation that 42.04.02 develops in full. $□$

Proposition 5 (Rogers' isomorphism, statement and proof sketch). Any two acceptable numberings $ν, ν^{'}$ are related by a computable bijection $π$ with $ν^{'} = ν \circ π$ .

Proof. Acceptability gives total computable translators $t, t^{'}$ with $ν_{e}^{'} = ν_{t (e)}$ and $ν_{e} = ν_{t^{'} (e)}^{'}$ , obtained by feeding one numbering's universal function through the other's s-m-n. By the padding lemma each numbering supplies, computably and uniformly, infinitely many indices of any given function, so $t$ and $t^{'}$ can be thinned to injections with computable ranges. A back-and-forth construction interleaves $t$ and $t^{'}$ : at each stage extend the partial bijection $π$ by matching a least unmatched index on one side to a fresh padded index on the other realising the same function. The construction is computable, total (every index is eventually matched), and bijective, and it preserves the computed function at every step, so $ν^{'} = ν \circ π$ . $□$

Connections Master

The halting problem 42.04.02 is the first and decisive consequence of the model fixed here: it diagonalises against the enumeration ${φ_{e}}$ using the universal function $U$ of this unit. The set $K = {e : φ_{e} (e) ↓}$ is c.e. but undecidable (proved in skeleton as Proposition 4), and co-produced unit 42.04.02 develops the reduction theory — many-one and Turing reducibility, $K$ as $Σ_{1}$ -complete — on top of the universal machine and s-m-n established here. That unit owns the undecidability results; this unit owns the model they are stated against.
Representability and Gödel's first incompleteness theorem 42.01.08 pending depend on this fixed notion of computability: a consistent, computably axiomatised theory extending Robinson arithmetic represents exactly the computable relations, so the c.e./computable distinction drawn here becomes the $Σ_{1}$ / $Δ_{1}$ distinction inside arithmetic. The co-produced unit 42.01.08 pending uses the recursion theorem and the enumeration ${φ_{e}}$ from this unit to build the self-referential sentence; the diagonal lemma there is the arithmetised twin of the fixed-point theorem proved here as Proposition 3.
The arithmetical hierarchy 42.04.05 is the upward continuation of the computable/c.e. dichotomy: the computable sets are $Δ_{1}$ , the c.e. sets are $Σ_{1}$ , and alternating the unbounded quantifier (the logical shadow of the $μ$ -operator) climbs to $Σ_{n}$ and $Π_{n}$ . That unit relativises the universal function and s-m-n of this unit to oracles, turning the bare model into the Turing-degree structure; the Kleene normal form proved here is the $n = 1$ base case of the hierarchy's quantifier-counting.
Algorithmic complexity and big-O 25.03.01 sits deliberately outside this unit: it adds a Blum complexity measure (Theorem 4) on top of the already-fixed model, asking not whether a function is computable but at what resource cost, and develops $P$ , $NP$ , and the polynomial hierarchy. The connection is by contrast and layering — computability theory says whether, complexity theory says how expensively — and the Blum axioms are the exact interface that keeps the two subjects separate while letting each build on the same Turing machine.

Historical & philosophical context Master

The decade 1931-1936 produced three independent analyses of effective calculability that turned out to coincide. Alonzo Church, working with Stephen Kleene, proposed in 1936 that the effectively calculable functions are precisely the $λ$ -definable functions, shown equal to the general recursive functions of Jacques Herbrand and Kurt Gödel; on that basis Church exhibited an unsolvable problem of elementary number theory and the undecidability of first-order validity ^{[Church 1936]}. In the same year Alan Turing, then unaware of Church's work, analysed computation by reducing a human computer following fixed rules to the operations of an abstract machine reading and writing a tape, and proved the unsolvability of the Entscheidungsproblem; Turing's appendix established that his machine-computable functions are exactly Church's $λ$ -definable ones. Emil Post independently described a closely related "worker following instructions" model the same year.

Gödel, initially reluctant to accept any single formal definition as capturing the informal notion, was persuaded by Turing's machine analysis specifically — he regarded it, unlike the equational or $λ$ -calculus definitions, as a direct conceptual analysis of "mechanical procedure" rather than a technical stipulation. The convergence of $λ$ -definability, general recursiveness, and Turing computability onto one class is the evidence for what Kleene later named the Church-Turing thesis: the identification is not a theorem, since one side is informal, but the robustness of the class under wholly different formalisations, together with Turing's analysis of what a rule-following agent can do, is taken as compelling. Kleene's Introduction to Metamathematics (1952) systematised the recursive-function side, the normal form theorem, and the enumeration; Hartley Rogers' 1967 text fixed the modern theory of acceptable numberings and index sets, and Manuel Blum's 1967 axioms separated the resource-free notion of computability from the complexity theory that grew from it.

Bibliography Master

@article{church1936unsolvable,
  author  = {Church, Alonzo},
  title   = {An unsolvable problem of elementary number theory},
  journal = {American Journal of Mathematics},
  volume  = {58},
  number  = {2},
  year    = {1936},
  pages   = {345--363}
}

@article{turing1936computable,
  author  = {Turing, Alan M.},
  title   = {On computable numbers, with an application to the {Entscheidungsproblem}},
  journal = {Proceedings of the London Mathematical Society},
  volume  = {s2-42},
  number  = {1},
  year    = {1937},
  pages   = {230--265}
}

@article{post1936finite,
  author  = {Post, Emil L.},
  title   = {Finite combinatory processes---formulation 1},
  journal = {The Journal of Symbolic Logic},
  volume  = {1},
  number  = {3},
  year    = {1936},
  pages   = {103--105}
}

@article{kleene1936general,
  author  = {Kleene, Stephen C.},
  title   = {General recursive functions of natural numbers},
  journal = {Mathematische Annalen},
  volume  = {112},
  year    = {1936},
  pages   = {727--742}
}

@article{blum1967machine,
  author  = {Blum, Manuel},
  title   = {A machine-independent theory of the complexity of recursive functions},
  journal = {Journal of the ACM},
  volume  = {14},
  number  = {2},
  year    = {1967},
  pages   = {322--336}
}

@book{soare2016turing,
  author    = {Soare, Robert I.},
  title     = {Turing Computability: Theory and Applications},
  series    = {Theory and Applications of Computability},
  publisher = {Springer},
  year      = {2016}
}

@book{rogers1967theory,
  author    = {Rogers, Hartley},
  title     = {Theory of Recursive Functions and Effective Computability},
  publisher = {McGraw-Hill},
  year      = {1967}
}

@book{odifreddi1989classical,
  author    = {Odifreddi, Piergiorgio},
  title     = {Classical Recursion Theory, Volume I},
  series    = {Studies in Logic and the Foundations of Mathematics},
  volume    = {125},
  publisher = {North-Holland},
  year      = {1989}
}

Prerequisites

none — this is a leaf unit

Tier anchors

beginner: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 1 (read the informal description of a machine reading and rewriting a tape, and the notion of a procedure that may run forever); Sipser 2013 *Introduction to the Theory of Computation* 3e (Cengage) §3.1 for the Turing-machine picture before any encoding
intermediate: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 1-2 (Turing machines, configurations, the partial recursive functions, the basic functions, primitive recursion and the $\mu$-operator, the universal machine, the enumeration $\{\varphi_e\}$, the s-m-n theorem, the padding lemma); Cutland 1980 *Computability: An Introduction to Recursive Function Theory* (Cambridge) Ch. 1-4
master: Soare 2016 *Turing Computability: Theory and Applications* (Springer) Ch. 1-3 and the historical notes (the equivalence of models, the Church-Turing thesis as a thesis, the universal machine and the acceptable numbering, s-m-n and the recursion theorem); Odifreddi 1989 *Classical Recursion Theory, Volume I* (North-Holland) Ch. I-II (acceptable numberings, the isomorphism theorem of Rogers, the Blum axioms separating computability from complexity); Rogers 1967 *Theory of Recursive Functions and Effective Computability* (McGraw-Hill) Ch. 1-5

References

Soare, R. I. — Turing Computability: Theory and Applications · Springer, Theory and Applications of Computability (2016). Ch. 1 develops the Turing machine as a finite control reading a two-way infinite tape, configurations and the one-step transition, computation as a sequence of configurations, the computable (total) and partial-computable functions, and decidable (computable) sets via characteristic functions; Ch. 2 develops the partial recursive functions from the basic functions (zero, successor, projections) closed under composition, primitive recursion, and the $\mu$-operator (unbounded minimisation), proves the equivalence of Turing-computable and partial-recursive functions, states the Church-Turing thesis as an identification of these classes with the intuitively effectively computable functions, constructs a universal Turing machine and the standard enumeration $\{\varphi_e\}_{e\in\omega}$ of partial computable functions via Gödel numbering of machines, and proves the s-m-n (parametrisation) theorem and the padding lemma; the distinction between computable and computably enumerable sets, and the recursion theorem, follow in Ch. 2-3.
Odifreddi, P. — Classical Recursion Theory, Volume I · North-Holland, Studies in Logic and the Foundations of Mathematics 125 (1989). Ch. I-II: the partial recursive functions and the equivalence of the Turing-machine, register-machine, $\lambda$-calculus, and Herbrand-Gödel-Kleene equational models; the universal function and acceptable numberings (a numbering is acceptable iff it admits both a universal function and the s-m-n theorem); Rogers' isomorphism theorem that any two acceptable numberings are related by a computable permutation of indices; the padding lemma exhibiting infinitely many indices for each partial computable function; the Blum axioms isolating complexity measures as an extra structure on top of the bare notion of computability, marking the boundary with the big-O / resource theory.
Church, A. — An unsolvable problem of elementary number theory · American Journal of Mathematics 58 (1936), 345-363. Defines effective calculability with the $\lambda$-definable functions, identifies it with the general recursive functions of Herbrand-Gödel-Kleene, and advances the thesis that this class is the intuitive notion of effectively calculable; constructs an unsolvable problem of elementary number theory.

Estimated time

beginner: 20m
intermediate: 50m
master: 90m