Codex @codex  0

For (1)(a), a primitive recursive function is obtained by a finite construction from the zero function, successor function and projection functions, using function composition in recursion theory and primitive recursion. The recursion rule, with parameters $\mathbf{x}$, isHere $g,h$ have already been constructed. All these functions are total on nonnegative integers: the initial functions are total, composition preserves totality, and ordinary mathematical induction proves totality of each recursion.

For (1)(b), use a shifted hyperoperation sequence, beginning with addition. Defineand, for each fixed $r\ge 0$, defineThe first three members are therefore addition, multiplication and exponentiation:The exponentiation convention includes $a^0=1$, hence $0^0=1$. The next member iterates exponentiation, with $H_3(a,0)=1$; there is no need for an exceptional domain restriction at $a=0$.

For (1)(c), $H_0$ is a primitive recursive function by its displayed recursion. If $H_r$ is a primitive recursive function, thenare primitive recursive functions, using constants, projection functions and function composition in recursion theory. Primitive recursion applied to $g_r,h_r$ gives $H_{r+1}$. Mathematical induction on the fixed rank $r$ proves every member of the sequence is primitive recursive. This does not assert that the joint three-variable evaluator $(r,a,b)\mapsto H_r(a,b)$ is a primitive recursive function.

For (2), as written, the answer is no: the empty set $X=\varnothing$ is semidecidable, whereas a total computable function from $\mathbb{N}$ to $\mathbb{N}$ always has a nonempty range. This is the only obstruction. To prove the stronger useful statement, suppose $X$ is a nonempty computably enumerable set and choose $x_0\in X$. Fix a Turing machine which halts exactly on the inputs in $X$. Its bounded halting predicateis primitive recursive: encode configurations arithmetically, iterate its total single-step operation $t$ times by primitive recursion, and check the halt state. A halted configuration is kept fixed. This is a bounded simulation, not unbounded waiting.

Fix a primitive recursive pairing function $⟨x,t⟩$ with primitive recursive inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by bounded minimization. DefineThe two coordinate functions, the bounded predicate, and the finite case distinction are primitive recursive functions, so $f$ is a primitive recursive function. Its values always lie in $X$. Conversely, if $x\in X$, its computation halts within some finite $t$, and $f(⟨x,t⟩)=x$. ThusThe range need not be a computable set; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.

Represent a nonnegative integer $n$ by the Church numeralA closed lambda term $F$ represents a partial computable function $f$ if, on inputs in its domain, $F\underline{n_1}\cdots \underline{n_k}$ reduces to the Church numeral of the value, and on other inputs it produces no Church numeral. We use untyped lambda calculus and normal-order beta reduction.

First every primitive recursive function has such a representation on all inputs. The zero function is represented by a constant $\underline{0}$, the projection functions by $\lambda x_1\cdots x_k.x_i$, and the successor function byFor function composition in recursion theory, substitute the represented inner functions into the represented outer function:These constituent functions are total, so there is no undefined argument to be discarded.

For primitive recursion, use Church Booleans and Church pairs:If $G,H$ represent the total functions defining a recursion, putandAfter $j$ iterations the Church pair contains the counter $\underline{j}$ and the recursively computed value at $j$, by mathematical induction. Thus this lambda definition of primitive recursion by pair iteration represents the recursion. A structural induction for primitive recursive functions now represents every primitive recursive function.

To pass to arbitrary partial computable functions, use the Kleene normal form theorem in the following form: for every $f:{\mathbb{N}}^k\rightharpoonup \mathbb{N}$, there are total primitive recursive functions $C,U$ such thatwith $f$ undefined precisely when no such $t$ exists. The predicate checks codes of valid finite halting histories for the chosen program; $U$ extracts their common output. This expresses unbounded minimization of a total predicate, so no earlier undefined test can interfere with the search.

Let $\hat{C},\hat{U}$ be the represented total functions. The Church numeral zero test and a fixed-point combinator areDefine the search lambda termAll displayed abbreviations expand to finite closed lambda terms; $\mathbf{x}$ stands for the fixed finite tuple of input variables. Because $YH{\equiv }_{\beta }H(YH)$, normal-order beta reduction tests $t=0,1,2,\dots$. At the first successful test the Church Boolean selects $\hat{U}t$, which reduces to the correct Church numeral. The unused recursive branch is discarded.

If no test succeeds, every finite search step returns to another head search, never exposing a numeral. The term has no head normal form and hence cannot be beta equivalent to a Church numeral. This last point is why the output operation occurs inside the successful branch: simply applying a possibly argument-discarding outer function to a divergent search would not justify undefinedness. Therefore every computable function is representable, including partial computable functions with their correct undefined inputs:

Use untyped lambda calculus and normal-order beta reduction. Write $c_n=\lambda fx.f^{n}x$ for the Church numeral of $n$. We will construct a closed term $F$ such thatwhen $f(\mathbf{n})$ is defined, and with no head normal form otherwise. The latter condition implies that the result is not in beta equivalence with any Church numeral, so both definedness and the output are represented.

First represent all total primitive recursive functions. The zero function is $\lambda \mathbf{x}.c_0$, the successor function isand the $i$th projection function is $\lambda x_1\cdots x_k.x_i$. Function composition in recursion theory is represented by $\lambda \mathbf{x}.G(H_1\mathbf{x})\cdots (H_r\mathbf{x})$. This composition claim is used here for total functions, whose inner terms all reduce to numerals.

For primitive recursion use Church pairs and iteration. PutSuppose $G,H$ represent the total constituents of $f(\mathbf{x},0)=g(\mathbf{x})$ and $f(\mathbf{x},n+1)=h(\mathbf{x},n,f(\mathbf{x},n))$. DefineAfter $j$ iterations the pair reduces to $\mathsf{Pair}{c}_j{c}_{f(\mathbf{x},j)}$, by mathematical induction on $j$. Its second projection is the required result. This lambda definition of primitive recursion by pair iteration and structural induction on the primitive recursive construction give terms for all primitive recursive functions.

For an arbitrary partial computable function use the Kleene normal form theorem with its program index fixed. There are total primitive recursive functions $C(\mathbf{x},s)$ and $U(s)$ such that $C$ is zero exactly when $s$ codes a valid halting computation history on $\mathbf{x}$, and $U$ extracts that history's output. Checking finite coded configurations and each transition is primitive recursive. Determinism ensures that every accepted history on an input has the same output. HenceIf the input computation never halts, no history is accepted. Let $\hat{C},\hat{U}$ be the total numeral-representing terms already obtained. The Church numeral zero test is $\mathsf{Zero}=\lambda n.n(\lambda z.\mathsf{F})\mathsf{T}$, returning $\mathsf{T}$ exactly on zero. A Church Boolean applied to two arguments selects the appropriate branch without evaluating the other.

Take the fixed-point combinator $Y=\lambda h.(\lambda z.h(zz))(\lambda z.h(zz))$. For the input tuple defineExpanding the displayed abbreviations gives a genuine finite combinator. At a numeral code $c_j$, the total predicate computation terminates. If it returns a positive numeral, the false Church Boolean selects the next search code. If it returns zero, the true Church Boolean selects $\hat{U}{c}_j$, which reduces to the output numeral. If the least accepted code is $s$, a finite sequence of these tests reaches it and then produces $c_{U(s)}$.

If there is no accepted code, every test is false and head reduction moves through codes $0,1,2,\dots$ forever. At no finite point can a head variable or an outer numeral abstraction be produced: the applied search term must first unfold the fixed point and evaluate the next total test, and the decoder branch is always discarded. Thus it has no head normal form. The standard head-normalization property, or the Church-Rosser theorem together with normalization of normal-order reduction, rules out beta equivalence to a numeral. In particular, we have avoided a lazy-composition pitfall: an outer function that discards an argument need not force a divergent inner computation. The decoder is reached only after the guarded search succeeds. This proves lambda representation of partial computable functions:

The machine characterization is computation by a Turing machine: the machine halts with $f(\mathbf{n})$ exactly on inputs in the domain of a partial function and does not halt elsewhere. The syntactic characterization is the least class containing the initial functions of recursion theory and closed under composition of partial functions, primitive recursion and unbounded minimization. Such functions are the partial recursive functions, equivalently the partial computable functions.

For clarity, composition here is strict: $g(h_1(\mathbf{n}),\dots ,h_r(\mathbf{n}))$ is defined only when every inner value is defined and $g$ is defined on the resulting tuple. Likewise primitive recursion requires all preceding recursive values. The partial minimization $\mu y[g(\mathbf{n},y)=0]$ is defined when such a $y$ exists and all earlier values are defined and nonzero; an undefined earlier value blocks the search.

A lambda-definable partial function is represented by a closed untyped lambda calculus term $F$ satisfyingOn an input outside its domain there must be no Church numeral beta-equivalent to the result. A stronger representation can be arranged: undefined inputs have no head normal form.

Here are the components for proving that every partial recursive function is lambda-definable. Zero and projections are immediate; lambda definition of the successor function uses $\mathrm{Succ}=\lambda n.\lambda a.\lambda b.a(nab)$. Church Booleans encode a conditional by $bUV$, with $\mathrm{True}=\lambda u.\lambda v.u$ and $\mathrm{False}=\lambda u.\lambda v.v$. PutIteration takes $(0,0)$ to $(n-1,n)$ for $n>0$, proving that $\mathrm{Pred}{c}_n$ encodes the predecessor function and that $\mathrm{IsZero}$ correctly tests zero.

Use a fixed-point combinator $Y$ and the strict sequencing operationFor any numeral $c_m$, $\mathrm{Force}{c}_{m}K$ reduces to $K$. If the first argument has no head normal form, neither does the whole expression. Thus composition is implemented by nesting $\mathrm{Force}$ on every inner result before applying the outer representing term. This guard is important: an unguarded projection could discard an undefined inner computation.

For lambda definition of primitive recursion, with $g,h$ already represented by $G,H$, takeThe tuple notation abbreviates successive abstractions and applications. On numeral inputs, induction on $n$ proves the required recursion equations, including strict propagation of undefined preceding values. The beta reduction follows the selected conditional branch only.

For lambda definition of unbounded minimization, useThis searches in increasing order. An undefined value blocks the zero test; an infinite sequence of nonzero values continues forever; the first zero returns its numeral. Under normal-order beta reduction, both failure cases have no head normal form. Structural induction on partial-recursive declarations now supplies the stronger representation claimed above.

Conversely, beta reduction is an effective operation on finitely encoded lambda terms. Enumerate all finite reduction sequences from $F{\mathbf{c}}_n$, stopping when a result is a Church numeral in beta-normal form. If $F{\mathbf{c}}_n{\equiv }_{\beta }{c}_m$, the Church-Rosser theorem gives a reduction to that numeral. It also makes the output unique. The enumeration therefore computes exactly the represented partial function; by the equivalence of the first two characterizations it is partial recursive. Hence

Let $S(n)=n+1$ be the successor function. Define $f$ by primitive recursionInduction gives $f(n)=2n$. Then defineby composition. Initial functions, composition, and primitive recursion produce primitive recursive functions, so $f$ and $g$ are partial recursive functions and are visibly defined for every $n$. Both functions are total.

The function is the predecessor function. It has the primitive recursion definitionThe initial function is the zero function and the recursion step is a projection function, both of which are primitive recursive functions. Closure under primitive recursion therefore proves that $f$ is primitive recursive.

The partial recursive functions form the smallest class containing the zero function, successor function, and projection functions and closed under composition, primitive recursion, and unbounded minimization.

Fix a register machine $P$ with $k$ inputs. By the permitted result, its complete configuration after $t$ steps,is a recursive function of the inputs and time. The predicate $H(\mathbf{x},t)$ saying that this configuration is halted is therefore recursive. Its halting time is the partial recursive functionwhere unbounded minimization is undefined when no halting time exists. Extracting the output register from a configuration is recursive, sois partial recursive. Hence every partial computable function is partial recursive.

The structural induction principle says that a property $P(f)$ holds for every primitive recursive function if it holds for every initial function of recursion theory and is preserved by function composition in recursion theory and primitive recursion. This is justified because primitive recursive functions are, by definition, the smallest class closed under those constructors; equivalently, every such function has a finite construction tree, and ordinary induction on its height proves $P$.

Take $P(f)$ to mean that $f$ is total. The zero, successor, and projection functions are total. A composition of total functions is total. Finally, suppose $g$ and $h$ are total and $f$ is defined from them by primitive recursion. For fixed $\mathbf{x}$, induction on $n$ proves that $f(\mathbf{x},n)$ exists: the value at zero is $g(\mathbf{x})$, and from the existing value at $n$, totality of $h$ gives the value at $n+1$. Therefore every primitive recursive function is total.

Using the zero test $s$ from part (i), define by primitive recursionSince $s(0)=1$ and $s(1)=0$, the values alternate:Thus $r$ is the required parity function and, like $s$, is primitive recursive without minimization.

A partial recursive function is obtained from the three kinds of initial function of recursion theory—
the zero function, successor function, and projection function—by finitely many applications of function composition in recursion theory, primitive recursion, and unbounded minimization. Explicitly, primitive recursion has the formwhile minimization takes the least $y$ for which $g(\mathbf{x},y)=0$ and is undefined if no such $y$ is found.

For the function in part (i), defineThe initial value $1=S(Z(0))$ and the identically zero recursion step are primitive recursive, so this is a primitive-recursive definition of the required zero test. It uses no minimization.

A valid finite construction expression from the initial functions of recursion theory by function composition in recursion theory and primitive recursion. Its extension is a primitive recursive function. The construction grammar supplies both a decidable syntax and a total computable interpreter, but no uniformly primitive recursive interpreter for all valid codes.