= Solution
A <function in intension> is a finite description of a computation, such as a program or a formal construction expression. A <function in extension> is the resulting input-output map, including its domain if it is partial. Different descriptions may have the same extension: the programs that return $x$ directly and that compute $x+0$ describe the same <function>. Finite descriptions have <Gödel numbers>; equality of the resulting <partial computable functions> is a separate semantic question.
The <primitive recursive functions> are the smallest class of numerical <functions> containing the <zero functions>, the <successor function> and all <projection functions>, and closed under <function composition in recursion theory> and <primitive recursion>. More explicitly, from $g:\mathbb N^k\to\mathbb N$ and $h:\mathbb N^{k+2}\to\mathbb N$ the latter operation forms
$$
f(\mathbf x,0)=g(\mathbf x),\qquad f(\mathbf x,n+1)=h(\mathbf x,n,f(\mathbf x,n)).
$$
For <function composition in recursion theory>, an $m$-ary $g$ and $k$-ary $h_1,\ldots,h_m$ give $g(h_1(\mathbf x),\ldots,h_m(\mathbf x))$. Zero functions of all allowed arities can be included, with nullary zero included if arity $0$ is part of the coding convention. Every resulting <function> is total: the initial functions are total, <function composition in recursion theory> preserves totality, and <mathematical induction> on $n$ verifies totality of <primitive recursion>. Applying <structural induction for primitive recursive functions> then covers all construction expressions.
Use a fixed effective <Gödel numbering> of finite tagged construction trees with decidable decoding. A node is tagged as zero, successor, projection, composition, or recursion. The <primitive recursive syntax and arity checking> algorithm first checks that the input decodes as a finite tree, then works upwards from its leaves. A projection tag $(k,j)$ is legal exactly when $1\leq j\leq k$, with output arity $k$. A composition node declares its output arity $k$ and is legal when its outer child has arity $m$, there are exactly $m$ inner children, and each has arity $k$; its arity is $k$. The declared arity also handles the case $m=0$. A recursion node is legal when its base child has arity $k$ and its step child has arity $k+2$; its arity is $k+1$. Zero and successor tags have their declared arities. Ill-formed nodes are rejected. The process terminates because there are only finitely many nodes. Thus, for each fixed $i$,
$$
\boxed{D_i=\{p:p\text{ is a valid primitive-recursive construction of arity }i\}\text{ is decidable}.}
$$
This is a syntactic assertion about <functions in intension>. It does not assert that arbitrary machine indices computing <primitive recursive functions> form a decidable set. That extensional property is nontrivial, hence undecidable by <Rice theorem>. For an explicit reduction, given a program $e$ construct a program that, on every input, waits for $\varphi_e(e)$ to halt and then returns $0$. Its extension is a <primitive recursive function> if $e\in K$, and otherwise is nowhere defined and so is not a <primitive recursive function>. A decision procedure for this latter semantic set would decide the <diagonal halting set>.
Enumerate the decidable syntax set $D_1$ in increasing code order as $p_0,p_1,\ldots$. There are infinitely many such descriptions; iterating successor after a unary zero expression already supplies infinitely many. Let $F_p$ be the extension of a valid construction and define
$$
U(n,x)=F_{p_n}(x),\qquad \boxed{d(n)=U(n,n)+1.}
$$
To compute $U$, find $p_n$ by the syntax test and interpret its finite construction tree. Evaluate <function composition in recursion theory> by evaluating the children, and evaluate <primitive recursion> by the prescribed finite loop of length equal to its final input. Termination follows from the totality argument above, so $U$ and $d$ are <total computable functions>.
If $d$ were a unary <primitive recursive function>, some construction $p_j$ would have extension $d$. Then the <diagonal argument> gives
$$
d(j)=F_{p_j}(j)+1=d(j)+1,
$$
which is impossible. \b[The displayed $d$ is total and computable but not primitive recursive.] Repetitions of extensions in the enumeration cause no problem: every possible extension is represented, which is all the <diagonal argument> needs. The same argument shows that the two-variable interpreter $U$ cannot itself be <primitive recursive>.
Back to article page
