Recursive Functions, Enumerability & Equivalent Computation Models

Recursive-function theory describes computation without tapes, states, or source code. A program is built from a few numerical functions and closure operations; nontermination appears as an undefined value of a partial function. This austere model exposes three central facts: finite algorithms can be encoded by natural numbers, one universal evaluator can run any encoded algorithm, and some mechanically recognizable sets still have no total decision procedure.

Throughout, a partial $k$-ary function is written

$$f:\mathbb N^k\rightharpoonup\mathbb N.$$

$f(\vec x)\downarrow$ means the computation terminates with a value; $f(\vec x)\uparrow$ means it diverges. Totality is a semantic property of the function, not a promise automatically supplied by its definition.

Primitive recursion: total computation by bounded construction #

The primitive recursive functions are the smallest class containing:

1. Zero: $Z(x)=0$.
2. Successor: $S(x)=x+1$.
3. Projections: $P_i^k(x_1,\ldots,x_k)=x_i$.
4. Composition: substitute already-built functions into another.
5. Primitive recursion: from total $g$ and $h$, define

$$\begin{aligned} f(\vec x,0)&=g(\vec x),\\ f(\vec x,n+1)&=h(\vec x,n,f(\vec x,n)). \end{aligned}$$

The recursion parameter decreases from $n$ to $0$, so evaluation always terminates. Every primitive recursive function is total.

Addition illustrates why the schema is computational rather than circular:

$$\mathop{\mathrm{add}}(x,0)=x,\qquad \mathop{\mathrm{add}}(x,n+1)=S(\mathop{\mathrm{add}}(x,n)).$$

Multiplication is primitive recursion over addition; exponentiation is primitive recursion over multiplication. Booleans, comparisons, bounded sums and products, finite sequences, and bounded searches can all be encoded the same way.

Primitive recursive does not mean "easy" or "small." It is a structural class, not a complexity class. Its functions can grow extraordinarily fast. Yet it still omits total computable functions such as the Ackermann function; diagonalizing over all primitive-recursive definitions produces growth that escapes every fixed primitive-recursive construction.

Unbounded minimization introduces partiality #

The $\mu$ operator searches without a supplied bound:

$$(\mu y)[R(\vec x,y)] = \text{the least }y\text{ such that }R(\vec x,y),$$

and is undefined if no witness is ever found. Adding unbounded minimization to the primitive recursive functions yields the partial recursive (or $\mu$-recursive) functions. A partial recursive function that happens to be total is called a general recursive function in the classical terminology.

For a minimal example, let

$$\mathop{\mathrm{pred}}^{-1}(n)=(\mu y)[n=y+1].$$

It returns $n-1$ for $n>0$ and searches forever for $n=0$. A finite machine can implement exactly that behavior: test $y=0,1,2,\ldots$ in order, halting at the first match.

The same operator captures semidecision. If $T(e,x,s)$ is a decidable predicate meaning "step-coded history $s$ is a valid halting computation of program $e$ on input $x$," then

$$(\mu s)[T(e,x,s)]$$

terminates exactly when program $e$ halts on $x$. The undefined cases are not defects in the formalism; they are how it represents nontermination faithfully.

flowchart TD
    B["Zero, successor, projections"] --> C["Composition"]
    C --> PR["Primitive recursion"]
    PR --> TOTAL["Primitive-recursive functions — always total"]
    TOTAL --> MU["Add unbounded minimization μ"]
    MU --> PARTIAL["Partial-recursive functions — may diverge"]
    PARTIAL --> GEN["Restrict to functions that are total"]
    GEN --> GENERAL["General-recursive functions"]

Coding finite objects as numbers #

Numerical models are not confined to intrinsically numerical tasks. Strings, trees, machine configurations, and finite computation histories can be effectively encoded as natural numbers. Pairing functions encode two numbers as one; repeated pairing encodes tuples and sequences. The encoding must support computable operations such as length, indexing, concatenation, and validation.

This yields an effective enumeration

$$\varphi_0,\varphi_1,\varphi_2,\ldots$$

of all partial recursive functions: $e$ is a program index and $\varphi_e(x)$ is the result of running program $e$ on $x$. Different numbering schemes assign different indices, but acceptable schemes preserve universal interpretation and effective program manipulation.

Kleene's normal-form theorem sharpens the picture. There are primitive recursive predicates/functions $T$ and $U$ such that every partial recursive function can be written schematically as

$$\varphi_e(x)=U\bigl(\mu s\,T(e,x,s)\bigr).$$

$T$ checks whether $s$ is a valid completed computation record; $U$ extracts its output. All unbounded behavior is concentrated in the search for a completed history, while checking and decoding remain primitive recursive.

Decidable and computably enumerable sets #

For $A\subseteq\mathbb N$:

• $A$ is decidable (recursive) if its characteristic function $\chi_A$ is total computable: it returns $1$ for members and $0$ for nonmembers.
• $A$ is computably enumerable (c.e.; historically recursively enumerable) if some partial computable recognizer halts and accepts exactly the members of $A$. On a nonmember it may reject or run forever.
• Equivalently, $A$ is c.e. if it is the domain of a partial recursive function, or the range of an effective enumerator (with minor conventions for the empty set).

The bridge between recognition and enumeration uses dovetailing. To enumerate the set recognized by $M$, do not run $M(0)$ to completion before trying $M(1)$—the first run may never stop. At stage $s$, execute one more step of each computation $M(0),\ldots,M(s)$ and emit inputs that have accepted. Every accepting run eventually gets its finite amount of time.

Two closure facts are diagnostic:

1. c.e. sets are closed under union and intersection, but not under complement.
2. $A$ is decidable iff both $A$ and its complement are c.e. Run the two recognizers in dovetailing fashion; exactly one must eventually accept.

The halting set: enumerable but undecidable #

Define

$$K=\{\langle e,x\rangle:\varphi_e(x)\downarrow\}.$$

$K$ is c.e.: simulate program $e$ on $x$ and accept if it halts. Suppose a total decider $H(e,x)$ for $K$ existed. Construct a program $D(e)$ that loops when $H(e,e)$ says "halts" and halts when it says "does not halt." Then:

• if $H(d,d)$ says $D(d)$ halts, $D(d)$ loops;
• if it says $D(d)$ does not halt, $D(d)$ halts.

Both cases contradict correctness, so no such $H$ exists. The complement of $K$ is therefore not c.e.; otherwise $K$ and its complement would make $K$ decidable.

Equivalent models and the Church–Turing thesis #

Several models developed from different intuitions compute the same partial functions after effective encoding:

• Turing machines manipulate symbols by local state transitions.
• Partial recursive functions build number functions from equations and minimization.
• Untyped lambda calculus computes by substitution and $\beta$-reduction.
• Register machines use finitely many unbounded counters.
• Post systems and normal Markov algorithms rewrite strings by finite rule sets.

Equivalence between any two formal models is a theorem: compile programs from one model into the other and prove that termination and output are preserved. The Church–Turing thesis is different. It identifies the informal notion of an effectively calculable procedure with Turing-computable/partial-recursive computation. Because one side is informal, the thesis is supported by convergence of models and robust experience, not proved as an ordinary equivalence theorem.

How to prove computability—or noncomputability #

For a positive result:

1. Fix a precise encoding of inputs and outputs.
2. Build the function from known recursive operations, or give a machine/program and prove equivalence.
3. State whether it is partial or total.
4. If total, provide a termination argument; syntax containing $\mu$ does not establish totality.

For a negative result:

1. Assume a decider or total function for the target problem.
2. Use it to decide a known undecidable set, usually through an effective mapping.
3. Preserve both yes and no instances; a one-way implication is insufficient.
4. Conclude that the assumed procedure cannot exist.

Diagonalization works because programs are both actors and finite data: once programs can be enumerated and interpreted, a constructed program can disagree with the alleged universal table on its own index. Gödel numbering, the universal evaluator, the halting set, and incompleteness are different manifestations of that same self-application boundary.