Recursive Functions

Three main classes:
- Primitive recursive functions (total, guaranteed termination).
- Gödel-Herbrand general recursive functions (defined by systems of equations).
- Partial recursive functions ($\mu$-recursive, allow partiality).
Key theorem: Partial recursive functions = Turing-computable functions.
Church's Thesis: Effectively calculable functions $\triangleq$ partial recursive functions.

Primitive Recursive Functions

Base functions:
- Zero: $$ \mathcal{O}: \mathbb{N}^0 \to \mathbb{N}, \emptyset \mapsto 0 $$
- Successor: $$ \text{succ}: \mathbb{N} \to \mathbb{N}, x \mapsto x + 1 $$
- Projection: $$ \pi_i^n: \mathbb{N}^n \to \mathbb{N}, (x_1, \dots, x_n) \mapsto x_i $$
Closure operations:
- Composition: If $f: \mathbb{N}^k \to \mathbb{N}$ and $g_i: \mathbb{N}^n \to \mathbb{N}$ are primitive recursive, then so is: $$ h(\vec{x}) = f(g_1(\vec{x}), \dots, g_k(\vec{x})) $$
- Primitive recursion: If $f: \mathbb{N}^n \to \mathbb{N}$ and $g: \mathbb{N}^{n+2} \to \mathbb{N}$ are primitive recursive, then so is $h = \text{pr}(f;g): \mathbb{N}^{n+1} \to \mathbb{N}$ defined by: $$ h(\vec{x}, 0) = f(\vec{x}) $$ $$ h(\vec{x}, y+1) = g(\vec{x}, h(\vec{x}, y), y) $$
Properties:
- Every primitive recursive function is total.
- Every primitive recursive function is Turing-computable.

Addition:
- $ \text{add}(x, 0) = x $
- $ \text{add}(x, y+1) = \text{succ}(\text{add}(x, y)) $
Multiplication:
- $ \text{mult}(x, 0) = 0 $
- $ \text{mult}(x, y+1) = \text{add}(x, \text{mult}(x, y)) $
Constant functions: $C_k^n(\vec{x}) = k$ are primitive recursive (by repeated composition of succ and $\mathcal{O}$).
Sign function:
- $ \text{sg}(0) = 0 $
- $ \text{sg}(y+1) = 1 $
Representing functions for predicates: Equality and less-than are primitive recursive.

Not all computable functions are primitive recursive.
Proof: Diagonalisation argument – there exist Turing-computable functions that grow faster than any primitive recursive function.
Ackermann function (simplified by Rósza Péter): $$ A(0, y) = y + 1 $$ $$ A(x+1, 0) = A(x, 1) $$ $$ A(x+1, y+1) = A(x, A(x+1, y)) $$
Growth rates: $$ A(0, n) = n + 1 $$ $$ A(1, n) = n + 2 $$ $$ A(2, n) = 2n + 3 $$ $$ A(3, n) = 2^{n+3} - 2 $$ $$ A(4, n) = \underbrace{2^{2{\cdot^{\cdot{2^{16}}}}}}_{n} - 3 $$
Theorem: The Ackermann function is not primitive recursive.
Busy Beaver connection (Green, 1964): $$ BB(2n) \geq A(n, n) $$

Defined by systems of recursion equations (like those for the Ackermann function).
Numerals: $ \langle 0 \rangle := 0 $, and $ \langle n+1 \rangle := \text{succ}(\langle n \rangle) $.
Definition: A function $f: \mathbb{N}^k \to \mathbb{N}$ is general recursive if it can be defined by a system $S$ of equations via a function symbol $F$ such that for all $n_1, \dots, n_k$, the expression $F(\langle n_1 \rangle, \dots, \langle n_k \rangle)$ evaluates uniquely to the numeral $\langle f(n_1, \dots, n_k) \rangle$.

Extend primitive recursive functions with the unbounded minimisation operator ($\mu$).
Definition: If $g: \mathbb{N}^{n+1} \to \mathbb{N}$ is primitive recursive, then: $$ f(\vec{x}) = \mu y \, [g(\vec{x}, y) = 0] $$ where $f(\vec{x})$ is the least $y$ such that $g(\vec{x}, y) = 0$, if such $y$ exists; otherwise $f$ is undefined.
Note: This introduces partiality – not all inputs yield a result.
Proposition: Every partial recursive function is Turing-computable.

Kleene's Normal Form Theorem: For every Turing-computable partial function $h: \mathbb{N}^k \to \mathbb{N}$, there exist primitive recursive functions $f: \mathbb{N} \to \mathbb{N}$ and $g: \mathbb{N}^{k+1} \to \mathbb{N}$ such that: $$ h(\vec{x}) = f(\mu y \, [g(\vec{x}, y) = 0]) $$
Theorem: The class of Turing-computable (partial) functions is exactly the class of partial recursive functions.

Church (1936): "We now define the notion [...] of an effectively calculable function of positive integers by identifying it with the notion of a recursive function of positive integers."
Formal definition (Church):
- A total function $f: \mathbb{N} \to \mathbb{N}$ is effectively calculable $\iff$ it is recursive.
- A partial function $g: \mathbb{N} \to \mathbb{N}$ is effectively calculable $\iff$ it is partial recursive.
Post's view (1936): Treated Church's identification as a "working hypothesis" needing continual verification.
Church's response to Post (1937): Argued that effectiveness has not been given an exact definition, so the "working hypothesis" has no exact meaning. Defining effectiveness as computability by an arbitrary finite machine adequately represents the ordinary notion.

Let $T$ be a computable and arithmetically sound axiomatic theory. Then there exists a constant $m_T$ such that for all $n \ge m_T$, no statement of the form "$BB(n) = k$" can be proved in $T$.
Concrete undecidable connections:
- There is an explicit 748-state TM that halts iff ZF is inconsistent. Thus, assuming ZF is consistent, ZF cannot prove $BB(748)$.
- There is an explicit 27-state TM that halts iff Goldbach's Conjecture is false.
- There is an explicit 744-state TM that halts iff the Riemann Hypothesis is false.

Primitive recursive: Total, guaranteed termination, but incomplete (cannot express all computable functions).
General recursive: Defined by equation systems; corresponds to total recursive functions.
Partial recursive: Allows unbounded search ($\mu$-operator); exactly captures Turing-computability.
Church's Thesis: Identifies intuitive effective calculability with formal recursiveness (accepted as the standard).
Ackermann function: A concrete example of a total computable function that is not primitive recursive.
Busy Beaver: Non-computable and connected to undecidable statements in arithmetic.