Recursive Functions and Church's Thesis

The incompleteness and undecidability theorems were stated for recursive sets and functions and then proved by exhibiting Gödel numberings under which the relevant syntactic operations came out recursive. That argument used the class without examining it.

Two definitions of recursive are in play, and they define the same class. One is internal to logic — representability in a weak arithmetic — and was established while building the subtheory. The other is the operator calculus of initial functions and closure rules that matches the standard presentation of computability. Church's thesis then identifies both with effective calculability.

Recursive relations and functions

A relation on $N$ is recursive when it can be captured, positively and negatively, by a formula deducible from a finite arithmetic. The reference theory is $A_{E}$ , the finite list of arithmetic axioms whose deductive closure $Cn A_{E}$ decides every numeral instance of a suitable formula.

Representability differs from definability in exactly one respect: definability asks whether a sentence is true in the standard structure $N$ , representability asks whether it is deducible from the axioms. Because $N$ is a model of $A_{E}$ , deducibility implies truth, so every representable relation is definable; the converse fails, and the gap between the two is the entire subject of incompleteness.

Functions reduce to relations through their graphs. A function $f : N^{m} \to N$ is functionally represented by $φ$ when $A_{E}$ proves not only $φ (S^{a_{1}} 0, \dots, S^{a_{m}} 0, S^{f (a)} 0)$ but also the uniqueness clause $\forall v_{m + 1} [φ (\dots, v_{m + 1}) \leftrightarrow v_{m + 1} = S^{f (a)} 0]$ .

A representable function is automatically functionally representable: given a formula $θ$ representing the graph, the sharpened formula

φ \equiv θ (v_{1}, v_{2}) \land \forall z (z < v_{2} \to \neg θ (v_{1}, z))

picks out the least witness and $A_{E}$ proves its uniqueness. So there is no distinction between relations that happen to be functions and functions proper.

The initial functions and the closure operators

The representable functions form a class closed under three operations, starting from three primitive functions. This is the operator characterization of recursiveness, and it is what the standard development of computability takes as its definition.

The initial functions are each representable by an equation, hence recursive outright:

Zero. The constant $Z (a) = 0$ , and more generally each constant function $C_{b}^{m} (a) = b$ , represented by $v_{m + 1} = S^{b} 0$ .
Successor. $S (a) = a + 1$ , represented by $v_{2} = S v_{1}$ .
Projections. $I_{i}^{m} (a_{1}, \dots, a_{m}) = a_{i}$ for $1 \leq i \leq m$ , represented by $v_{m + 1} = v_{i}$ .

The class is closed under three operators. Each closure fact was proved for $Cn A_{E}$ by constructing, from formulas representing the inputs, a formula representing the output.

The minimization (or least-zero) operator $μ$ is the one that reaches beyond primitive recursion. A function built from the initial functions using only composition and primitive recursion is primitive recursive; adding $μ$ applied to primitive recursive functions, with the totality proviso guaranteeing a zero exists, yields the full class of recursive functions. Every primitive recursive function is total, whereas $μ$ can be applied even when no zero is guaranteed, producing the partial recursive functions discussed below.

The four classes nest. The three initial functions generate the primitive recursive functions under composition and primitive recursion; adding total minimization gives the recursive functions; dropping the totality proviso on minimization gives the partial recursive functions.

The recursive functions are the least class containing the three initial functions and closed under composition, primitive recursion, and minimization; the primitive recursive functions omit the last operator.

Primitive recursion computes a function's value at $a + 1$ from its value at $a$ together with the coding of all earlier values. Unrolling the recursion is a finite computation of exactly $a$ steps.

Primitive recursion computes the value at each argument from the previous value by applying g, a finite unrolling that terminates in a steps.

Worked example. Addition, multiplication, and factorial are built by primitive recursion, each unrolled on a small input. Addition recurses on the first argument with base value $b$ and step $S$ :

add (0, b) = b, add (a + 1, b) = S (add (a, b)) .

Unrolling at $a = 2, b = 3$ gives $add (0, 3) = 3$ , $add (1, 3) = S (3) = 4$ , $add (2, 3) = S (4) = 5$ , so $2 + 3 = 5$ . Multiplication recurses with base $0$ and a step that adds $b$ , reusing addition:

mult (0, b) = 0, mult (a + 1, b) = add (mult (a, b), b) .

Unrolling at $a = 2, b = 3$ gives $mult (0, 3) = 0$ , $mult (1, 3) = 0 + 3 = 3$ , $mult (2, 3) = 3 + 3 = 6$ , so $2 \cdot 3 = 6$ . Factorial reads the running argument $a$ that the schema hands to the step function:

fact (0) = 1, fact (a + 1) = (a + 1) \cdot fact (a) .

Unrolling gives $fact (1) = 1 \cdot 1 = 1$ , $fact (2) = 2 \cdot 1 = 2$ , $fact (3) = 3 \cdot 2 = 6$ , $fact (4) = 4 \cdot 6 = 24$ , so $4! = 24$ . Each unrolling terminates in exactly $a$ applications of the step function.

The catalog built during the subtheory construction supplies the concrete instances: addition, multiplication, the sequence-coding and decoding functions, the length and concatenation functions, the prime-listing function, and the bounded quantifiers. Every relation with a quantifier-free definition in $N$ is representable, and the representable relations are closed under union, intersection, complement, and bounded quantification.

Characteristic functions and relations

A relation and its characteristic function are recursive together, so the operator calculus applies to sets as well as to functions.

One direction: if $ψ (v_{1}, v_{2})$ represents $K_{R}$ , then $ψ (v_{1}, S 0)$ represents $R$ . The other: if $φ$ represents $R$ , then $(φ \land v_{2} = S 0) \lor (\neg φ \land v_{2} = 0)$ represents the graph of $K_{R}$ . Deciding membership in $R$ and computing $K_{R}$ are the same problem in two notations.

Church's thesis

Recursiveness was defined syntactically, through deducibility. The claim that it is the right formalization of effectively computable is not a theorem — the informal notion has no mathematical definition to prove things about — but a judgment supported by convergent evidence.

The situation parallels the $ε$ – $δ$ definition of continuity: a precise notion is offered as the counterpart of an intuitive one, and one asks whether the fit is good. If anything the recursive class is too generous, admitting decision procedures whose running time and memory make any actual implementation absurd. Recursiveness models decidability in an idealized setting where computation length and storage are ignored.

Two lines of evidence support the identification:

Nothing decidable has escaped. Every relation mathematicians have judged decidable has turned out to be recursive.
Every model of computation agrees. Turing machines (1936), Post's systems, the $λ$ -calculus, and register machines all generate exactly the recursive functions. Because Turing's analysis of effective procedure is the most direct, the principle is often called the Church–Turing thesis.

Register machines

The register machine, one of the equivalent models, is concrete and easy to program. A register machine has finitely many registers $1, 2, \dots, K$ , each holding a natural number of unbounded size, and runs a fixed program of three instruction types.

Instruction	Written	Effect
Increment	$I r$	add $1$ to register $r$ , then continue
Decrement	$D r$	if register $r$ is nonzero, subtract $1$ and skip the next instruction; if zero, continue
Transfer	$T q$	jump $q$ instructions forward ( $q \geq 0$ ) or backward ( $q < 0$ ); halt if none exists

The decrement instruction's conditional skip is the machine's only branching mechanism, and it is enough. A short program clears a register by decrementing in a loop; a longer one moves a number between registers; addition of two registers takes twenty-seven instructions. A partial function $f$ is calculated by a program $P$ when, started with $a$ in the first registers, the machine halts with $f (a)$ in register $n + 1$ if $f (a)$ is defined, and runs forever if it is not.

Both directions go through arithmetization. To show a machine-calculable function is recursive, one assigns Gödel numbers to programs and to sequences of memory configurations — exactly as deductions were arithmetized — and checks that $y$ codes a halting computation of program $e$ on input $a$ is a recursive relation. The converse re-runs the catalog with calculable by a register machine in place of representable, using that the recursive functions are generated from a fixed handful by composition and minimization. Deductions and computations arithmetize the same way: each is a finite sequence of steps, and each step is checkable by a recursive test.

Recursively enumerable sets

Below the recursive sets lies a strictly larger class: the sets one can list, but not necessarily decide.

An r.e. set is one existential quantifier away from recursive, and several equivalent forms make this precise.

Every recursive relation is r.e., since a quantifier over a variable that does not occur adds nothing. The converse fails in general, and Post's theorem gives the criterion for when it holds.

If $R$ is recursive, so is its complement, and both are r.e. Conversely, run the two enumerations of $R$ and $\overline{R}$ in parallel; every $a$ appears in exactly one, and whichever list it surfaces in decides membership. So a set fails to be recursive precisely when it is r.e. but its complement is not.

Every recursive set is recursively enumerable; the halting set K lies in the r.e. region but outside the recursive core, and its complement escapes the r.e. class entirely.

The normal form theorem

Every recursive function is computed by a single universal scheme: search for a witness, then read off the answer. Kleene's normal form theorem builds this scheme out of one recursive relation and one recursive extraction function.

For each $m$ there is a recursive $(m + 2)$ -ary relation $T_{m}$ and a recursive function $U$ such that, taking $e$ to be the Gödel number of a formula weakly representing $f$ ,

f (a_{1}, \dots, a_{m}) = U (μ k ⟨ e, a_{1}, \dots, a_{m}, k ⟩ \in T_{m}) .

The relation $T_{m}$ holds when $e$ codes a suitable formula and $k$ codes a deduction from $A_{E}$ that pins the output value; $U$ extracts that value from $k$ . Only the search operator $μ$ stands between the recursive relation $T_{m}$ and the value of $f$ .

The universal scheme takes a program number e and input a, searches for the least witness k in the recursive relation, and reads the output off k with U; one machine computes every one-place recursive function.

Extending the scheme to functions that may diverge gives the recursive partial functions: for each index $e$ , the $m$ -place partial function

[[e]]_{m} (a) = U (μ k ⟨ e, a, k ⟩ \in T_{m}),

undefined when no such $k$ exists. Every recursive partial function equals $[[e]]_{m}$ for some $e$ , and this list $[[0]]_{1}, [[1]]_{1}, \dots$ indexes all one-place recursive partial functions. The universal function $Φ (e, a) = [[e]]_{1} (a)$ , which runs program $e$ on input $a$ , is itself a recursive partial function — the formal counterpart of an operating system that takes a program and its data and executes one on the other.

The halting problem

The index list yields an explicit r.e. non-recursive set, by diagonalization.

$K$ is r.e. because $a \in K \leftrightarrow \exists k ⟨ a, a, k ⟩ \in T_{1}$ , a recursive relation with one quantifier. Suppose $K$ were recursive. Then the function

g (a) = {[[a]]_{1} (a) + 1 0 a \in K, a \in / K,

would be total and recursive, hence $g = [[e]]_{1}$ for some $e$ . But $e \in K$ (since $g$ is total, $[[e]]_{1} (e)$ is defined), so $g (e) = [[e]]_{1} (e) + 1$ , contradicting $g (e) = [[e]]_{1} (e)$ . The complement $\overline{K}$ is therefore not r.e., and $K$ witnesses the strict inclusion recursive $⊊$ r.e.

Algorithm:

\textsc{Enumerate-}K

— lists exactly the halting inputs, never terminating on non-members

1
for each step $t = 0, 1, 2, \dots$ do
2
for each $a \le t$ do
3
if $\langle a, a, t\rangle \in T_1$ then
4
output $a$
program a halts on input a within the bound coded by t

This procedure lists every member of $K$ , but no analogous procedure lists $\overline{K}$ : a machine that could enumerate the non-halting inputs would, combined with $Enumerate- K$ , decide $K$ , which Post's theorem forbids. The diagonal set ${a : a \in / W_{a}}$ , where $W_{e} = dom ([[e]])_{1}$ runs through all r.e. sets, is exactly $\overline{K}$ , and it agrees with no $W_{e}$ because $q \in \overline{K} \leftrightarrow q \in / W_{q}$ .

Recursiveness is representability

The two definitions of recursive close into a single equivalence. The operator calculus, register machines, Turing machines, and representability in $Cn A_{E}$ all cut out the same class.

The two definitions of recursive coincide: representability in the finite arithmetic and closure under the operator calculus name the same class, with register and Turing machines confirming the fit from the computability side.

This equivalence is what the incompleteness argument rested on. Because the syntactic operations of a formal theory are recursive, they are representable, so a strong enough arithmetic can talk about its own provability — and the fixed-point construction then produces a true sentence the theory cannot prove. Read from the computability side, the same fact says $Th N$ is not recursively enumerable: were it r.e., $K$ would be, since membership in $K$ reduces to truth of an arithmetic sentence. No consistent, recursively axiomatized theory captures all of arithmetic truth.

One gap remains in this chain. The representability of the syntactic operations rested on the sequence-coding functions, and those were built with exponentiation and the prime-power encoding. Running the argument inside the language with addition and multiplication only requires representing exponentiation without the symbol $E$ , using a sequence encoder assembled from $+$ and $\cdot$ alone.