---
title: Recursive Functions and Church's Thesis
module: Recursive Functions and Representability
moduleNumber: 8
lessonNumber: 1
order: 801
summary: >
  The recursive functions are the formal counterpart of the effectively
  computable ones: built from three initial functions by composition,
  primitive recursion, and minimization, and equivalently the functions
  representable in a finitely axiomatized arithmetic. Church's thesis
  identifies the class with effective calculability; Kleene's normal form
  theorem and the unsolvable halting problem place the recursive sets strictly
  inside the recursively enumerable ones.
topics: [Recursive Functions and Representability]
sources:
  - book: Enderton
    ref: "Ch. 3 — Undecidability; §3.3 A Subtheory of Number Theory (representable functions, the catalog)"
  - book: Enderton
    ref: "§3.5 Incompleteness and Undecidability (recursive enumerability); §3.6 Recursive Functions"
draft: false
---

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](/logic/arithmetic-and-definability/a-subtheory-and-representability).
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 $\mathbb{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.

> **Definition (Representable relation).** A formula $\rho$, with only
> $v_1,\dots,v_m$ free, _represents_ an $m$-ary relation $R$ in
> $\Cn A_E$ iff for every $a_1,\dots,a_m \in \mathbb{N}$,
> $$
> \langle a_1,\dots,a_m\rangle \in R \;\Rightarrow\; A_E \vdash \rho(\mathsf{S}^{a_1}0,\dots,\mathsf{S}^{a_m}0),
> $$
> $$
> \langle a_1,\dots,a_m\rangle \notin R \;\Rightarrow\; A_E \vdash \neg\,\rho(\mathsf{S}^{a_1}0,\dots,\mathsf{S}^{a_m}0).
> $$
> Here $\mathsf{S}^a 0$ is the _numeral_ for $a$, the term $S(S(\cdots S(0)))$
> with $a$ applications of the successor symbol.

Representability differs from definability in exactly one respect: definability
asks whether a sentence is _true_ in the standard structure $\fN$,
representability asks whether it is _deducible_ from the axioms. Because
$\fN$ 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.

> **Definition (Recursive relation).** A relation $R$ on $\mathbb{N}$ is
> _recursive_ iff it is representable in some consistent, finitely axiomatizable
> theory in a language containing $0$ and $S$ — equivalently, representable in
> $\Cn A_E$.

Functions reduce to relations through their graphs. A function $f\colon
\mathbb{N}^m \to \mathbb{N}$ is _functionally represented_ by $\varphi$ when
$A_E$ proves not only $\varphi(\mathsf{S}^{a_1}0,\dots,\mathsf{S}^{a_m}0,
\mathsf{S}^{f(\vec a)}0)$ but also the uniqueness clause $\forall v_{m+1}\,[\,
\varphi(\dots,v_{m+1}) \leftrightarrow v_{m+1}=\mathsf{S}^{f(\vec a)}0\,]$.

> **Definition (Recursive function).** $f\colon \mathbb{N}^m \to \mathbb{N}$ is
> _recursive_ iff its graph $\{\langle \vec a, b\rangle : f(\vec a)=b\}$ is a
> recursive relation. Equivalently, $f$ is functionally representable in
> $\Cn A_E$.

A representable function is automatically functionally representable: given a
formula $\theta$ representing the graph, the sharpened formula
$$
\varphi \;\equiv\; \theta(v_1,v_2) \wedge \forall z\,(z<v_2 \to \neg\,\theta(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^m_b(\vec a)=b$, represented by $v_{m+1}=\mathsf{S}^b 0$.
- **Successor.** $S(a)=a+1$, represented by $v_2 = Sv_1$.
- **Projections.** $I^m_i(a_1,\dots,a_m)=a_i$ for $1\le i\le 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.

> **Theorem (Closure under composition).** If $g$ is an $n$-place recursive
> function and $h_1,\dots,h_n$ are $m$-place recursive functions, then
> $$
> f(\vec a) = g\big(h_1(\vec a),\dots,h_n(\vec a)\big)
> $$
> is recursive.

> **Theorem (Closure under primitive recursion).** If $g$ is recursive and $f$
> is the unique function satisfying
> $$
> f(0,\vec b) = k(\vec b), \qquad f(a+1,\vec b) = g\big(f(a,\vec b),\,a,\,\vec b\big)
> $$
> with $k$ recursive, then $f$ is recursive.

> **Theorem (Closure under minimization).** If the $(m{+}1)$-place function $g$
> is recursive and for every $\vec a$ there is a $b$ with $g(\vec a, b)=0$, then
> $$
> f(\vec a) = \mu b\,[\,g(\vec a, b)=0\,] = \text{the least } b \text{ with } g(\vec a, b)=0
> $$
> is recursive.

The minimization (or "least-zero") operator $\mu$ 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 $\mu$
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 $\mu$ can be applied even when no zero is
guaranteed, producing the _partial_ recursive functions discussed below.

$$
% caption: 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.
\begin{tikzpicture}[font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[draw=black] (-5,-3.4) rectangle (5,3.4);
  \node[black, anchor=north] at (0,3.28) {partial recursive};
  \draw[draw=acc, thick, fill=acc!8] (-4,-2.75) rectangle (4,2.65);
  \node[acc, anchor=north] at (0,2.52) {recursive (total)};
  \draw[draw=acc, fill=acc!13] (-2.95,-2.05) rectangle (2.95,1.75);
  \node[acc, anchor=north] at (0,1.62) {primitive recursive};
  \draw[draw=black, fill=white] (-1.75,-1.15) rectangle (1.75,0.85);
  \node[anchor=north, align=center, font=\scriptsize] at (0,0.72) {initial:\\zero, successor,\\projections};
\end{tikzpicture}
$$

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  base/.style={draw, minimum width=30mm, minimum height=26mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[base] (init) at (0,0) {\textbf{initial}\\[2pt]zero\\successor\\projections};
  \node[base, draw=acc, text=acc] (op) at (5,0) {\textbf{operators}\\[2pt]composition\\primitive recursion\\minimization};
  \node[base, draw=acc, thick] (out) at (10.2,0) {\textbf{recursive}\\\textbf{functions}};
  \draw[->, black, thick] (init) -- (op);
  \draw[->, acc, thick] (op) -- node[above, font=\scriptsize] {closure} (out);
  \draw[->, acc] (out.north) to[out=120,in=60,looseness=5] node[above, font=\scriptsize] {closed under} (out.north);
\end{tikzpicture}
$$

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.

$$
% caption: Primitive recursion computes the value at each argument from the
% previous value by applying g, a finite unrolling that terminates in a steps.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  cell/.style={draw, minimum width=16mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[cell] (f0) at (0,0)    {f(0)};
  \node[cell] (f1) at (2.4,0)  {f(1)};
  \node[cell] (f2) at (4.8,0)  {f(2)};
  \node[cell] (f3) at (7.2,0)  {f(3)};
  \node[font=\scriptsize] (dots) at (9.2,0) {$\cdots$};
  \node[cell, draw=acc, text=acc] (fn) at (11.4,0) {f(a)};
  \draw[->, acc] (f0) -- node[above, font=\scriptsize] {g} (f1);
  \draw[->, acc] (f1) -- node[above, font=\scriptsize] {g} (f2);
  \draw[->, acc] (f2) -- node[above, font=\scriptsize] {g} (f3);
  \draw[->, acc] (f3) -- node[above, font=\scriptsize] {g} (dots);
  \draw[->, acc] (dots) -- node[above, font=\scriptsize] {g} (fn);
  \node[font=\scriptsize, anchor=north] at (0,-0.7) {base value};
\end{tikzpicture}
$$

> **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$:
>
> $$
> \mathrm{add}(0,b)=b, \qquad \mathrm{add}(a+1,b)=S\big(\mathrm{add}(a,b)\big).
> $$
>
> Unrolling at $a=2,\ b=3$ gives $\mathrm{add}(0,3)=3$, $\mathrm{add}(1,3)=S(3)=4$,
> $\mathrm{add}(2,3)=S(4)=5$, so $2+3=5$. Multiplication recurses with base $0$ and
> a step that adds $b$, reusing addition:
>
> $$
> \mathrm{mult}(0,b)=0, \qquad \mathrm{mult}(a+1,b)=\mathrm{add}\big(\mathrm{mult}(a,b),\,b\big).
> $$
>
> Unrolling at $a=2,\ b=3$ gives $\mathrm{mult}(0,3)=0$, $\mathrm{mult}(1,3)=0+3=3$,
> $\mathrm{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:
>
> $$
> \mathrm{fact}(0)=1, \qquad \mathrm{fact}(a+1)=(a+1)\cdot\mathrm{fact}(a).
> $$
>
> Unrolling gives $\mathrm{fact}(1)=1\cdot 1=1$, $\mathrm{fact}(2)=2\cdot 1=2$,
> $\mathrm{fact}(3)=3\cdot 2=6$, $\mathrm{fact}(4)=4\cdot 6=24$, so $4!=24$. Each
> unrolling terminates in exactly $a$ applications of the step function.

> **Worked example.** The least-zero operator computes the integer square-root
> ceiling. Take $f(a)=\mu b\,[\,a \le b\cdot b\,]$, the least $b$ whose square is
> at least $a$; the search condition $a \le b\cdot b$ is a recursive relation, so
> $f$ is recursive. For $a=10$ the search steps through $b=0,1,2,\dots$ and reads
> off the successive squares
>
> $$
> 0\cdot 0=0,\quad 1\cdot 1=1,\quad 2\cdot 2=4,\quad 3\cdot 3=9,\quad 4\cdot 4=16,
> $$
>
> stopping at the first $b$ with $10 \le b\cdot b$, namely $b=4$, so $f(10)=4$.
> Some $b$ always satisfies $a \le b\cdot b$, so the totality proviso holds and
> $f$ is total.

The catalog built during
[the subtheory construction](/logic/arithmetic-and-definability/a-subtheory-and-representability)
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 $\fN$ 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.

> **Theorem (Characteristic function).** A relation $R$ is recursive iff its
> characteristic function
> $$
> K_R(\vec a) = \begin{cases} 1 & \vec a \in R,\\ 0 & \vec a \notin R,\end{cases}
> $$
> is recursive.

One direction: if $\psi(v_1,v_2)$ represents $K_R$, then $\psi(v_1,\mathsf{S}0)$
represents $R$. The other: if $\varphi$ represents $R$, then $(\varphi \wedge
v_2=\mathsf{S}0) \vee (\neg\varphi \wedge v_2=0)$ represents the graph of $K_R$.
Deciding membership in $R$ and computing $K_R$ are the same problem in two
notations.

> **Worked example.** The relation $\mathrm{Even}=\{a : a\text{ is even}\}$ is
> recursive, verified through numeralwise determination. The formula
>
> $$
> \varepsilon(v_1) \;\equiv\; \exists x\,(x \le v_1 \wedge v_1 = x + x)
> $$
>
> defines $\mathrm{Even}$ in $\fN$; its matrix is atomic, and bounded
> existential quantification preserves numeralwise determination by $A_E$. A
> formula that both defines a relation in $\fN$ and is numeralwise determined by
> $A_E$ represents that relation, so $\varepsilon$ represents $\mathrm{Even}$ in
> $\Cn A_E$. Two numeral instances confirm the decision, positively and
> negatively. For $a=4$ the witness $x=2$ makes $\mathsf{S}^4 0=\mathsf{S}^2 0+\mathsf{S}^2 0$
> a true variable-free equation, deducible from $A_E$, so
> $A_E \vdash \varepsilon(\mathsf{S}^4 0)$. For $a=5$ the axioms fix that
> $x \le \mathsf{S}^5 0$ holds only for $x \in \{0,1,2,3,4,5\}$, and they evaluate
> the candidate sums $0,2,4,6,8,10$ — none equal to $5$ — so
> $A_E \vdash \neg\varepsilon(\mathsf{S}^5 0)$.

## 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.

> **Church's thesis.** A relation is effectively decidable iff it is recursive;
> a function is effectively computable iff it is recursive. Equivalently, the
> recursive relations are exactly those represented in some consistent, finitely
> axiomatizable arithmetic.

The situation parallels the $\varepsilon$–$\delta$ 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 $\lambda$-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 | $\mathbf{I}\,r$ | add $1$ to register $r$, then continue |
| Decrement | $\mathbf{D}\,r$ | if register $r$ is nonzero, subtract $1$ and _skip_ the next instruction; if zero, continue |
| Transfer | $\mathbf{T}\,q$ | jump $q$ instructions forward ($q\ge 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 $\vec a$ in the first registers, the machine halts
with $f(\vec a)$ in register $n{+}1$ if $f(\vec a)$ is defined, and runs forever
if it is not.

> **Theorem (Register-machine equivalence).** A partial function is calculated by
> some register-machine program iff it is a recursive partial function.

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](/logic/incompleteness/arithmetization-of-syntax) —
and checks that "$y$ codes a halting computation of program $e$ on input $\vec
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.

> **Definition (Recursively enumerable).** A relation $R$ is _recursively
> enumerable_ (r.e.) iff it has the form
> $$
> R = \{\,\vec a : \exists b\ \langle \vec a, b\rangle \in Q\,\}
> $$
> for some recursive relation $Q$ — that is, $R$ is a recursive relation with one
> existential quantifier applied.

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

> **Theorem (Characterizations of r.e.).** For a relation $R$, the following are
> equivalent: (1) $R$ is recursively enumerable; (2) $R$ is the domain of a
> recursive partial function; (3) $R = \{\vec a : \exists b\ \langle \vec
> a,b\rangle \in Q\}$ for recursive $Q$; (4) $R$ is empty or the range of a total
> recursive function. Under Church's thesis, $R$ is r.e. iff it is effectively
> enumerable — a procedure lists its members, in some order, possibly with
> repetitions.

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.

> **Theorem (Post).** A relation $R$ is recursive iff both $R$ and its complement
> are recursively enumerable.

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 $\vec 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.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[black] (0,0) ellipse (5 and 3);
  \node[black, anchor=north east, font=\scriptsize] at (4.9,2.9) {recursively enumerable};
  \draw[fill=acc!10, draw=acc, thick] (-1.6,0) ellipse (2.6 and 2);
  \node[acc, font=\scriptsize] at (-1.6,0) {recursive};
  \fill[black] (2.6,0.2) circle (2pt);
  \node[anchor=west, font=\scriptsize] at (2.75,0.2) {halting set K};
  \node[anchor=north, font=\scriptsize, align=center] at (0,-3.15) {complement of K: not r.e.};
\end{tikzpicture}
$$

## 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\big(\mu k\ \langle e, a_1,\dots,a_m, k\rangle \in T_m\big).
$$

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 $\mu$ stands between the recursive relation $T_m$
and the value of $f$.

> **Theorem (Normal form, Kleene).** For every recursive $f\colon \mathbb{N}^m
> \to \mathbb{N}$ there is a number $e$ with $f(\vec a)=U(\mu k\,\langle e,\vec
> a,k\rangle\in T_m)$; conversely, whenever the search always succeeds, the
> function so defined is recursive.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=24mm, minimum height=10mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[box] (e) at (0,1)  {program e};
  \node[box] (a) at (0,-1) {input a};
  \node[box, draw=acc, text=acc, thick, minimum width=30mm] (t) at (4.4,0) {search least k\\with T-relation};
  \node[box] (u) at (9,0)  {output U(k)};
  \draw[->, acc] (e) -- (t);
  \draw[->, acc] (a) -- (t);
  \draw[->, acc] (t) -- node[above, font=\scriptsize] {witness k} (u);
\end{tikzpicture}
$$

Extending the scheme to functions that may diverge gives the **recursive partial
functions**: for each index $e$, the $m$-place partial function
$$
[\![e]\!]_m(\vec a) = U\big(\mu k\ \langle e,\vec a,k\rangle \in T_m\big),
$$
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
$\Phi(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.

> **Theorem (Unsolvability of the halting problem).** The set
> $$
> K = \{\,a : [\![a]\!]_1(a)\text{ is defined}\,\}
> $$
> is recursively enumerable but not recursive. Consequently the relation
> $\{\langle e,a\rangle : [\![e]\!]_1(a)\text{ is defined}\}$ is not recursive:
> no procedure decides, from a program and an input, whether the program halts.

$K$ is r.e. because $a\in K \iff \exists k\,\langle a,a,k\rangle \in T_1$, a
recursive relation with one quantifier. Suppose $K$ were recursive. Then the
function
$$
g(a) = \begin{cases} [\![a]\!]_1(a)+1 & a\in K,\\ 0 & a\notin K,\end{cases}
$$
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 $\subsetneq$ r.e.

```algorithm
caption: $\textsc{Enumerate-}K$ — lists exactly the halting inputs, never terminating on non-members
for each step $t = 0, 1, 2, \dots$ do
  for each $a \le t$ do
    if $\langle a, a, t\rangle \in T_1$ then
      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 $\textsc{Enumerate-}K$, decide $K$, which Post's theorem forbids.
The diagonal set $\{a : a\notin 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} \iff q\notin 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.

> **Theorem (Recursive equals representable).** A relation is recursive iff it is
> representable in $\Cn A_E$; a function is recursive iff it is
> functionally representable in $\Cn A_E$.

$$
% caption: 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.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=34mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[box, draw=acc, text=acc, thick] (rep) at (0,0)  {representable\\in the arithmetic};
  \node[box, draw=acc, text=acc, thick] (rec) at (6.4,0) {closed under the\\operators};
  \draw[->, acc, thick] (rep.north east) to[bend left=18] node[above, font=\scriptsize] {Theorem} (rec.north west);
  \draw[->, acc, thick] (rec.south west) to[bend left=18] node[below, font=\scriptsize] {Theorem} (rep.south east);
  \node[box, minimum width=30mm] (mac) at (3.2,-2.6) {register and Turing\\machines};
  \draw[->, black] (mac) -- (rep.south west);
  \draw[->, black] (mac) -- (rec.south east);
\end{tikzpicture}
$$

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](/logic/incompleteness/incompleteness-and-undecidability)
then produces a true sentence the theory cannot prove. Read from the
computability side, the same fact says $\Th \fN$ 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.