= Solution
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$, is
$$
f(\mathbf x,0)=g(\mathbf x),\qquad
f(\mathbf x,n+1)=h(\mathbf x,n,f(\mathbf x,n)).
$$
Here $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>. Define
$$
H_0(a,0)=a,\qquad H_0(a,b+1)=S(H_0(a,b)),
$$
and, for each fixed $r\geq0$, define
$$
H_{r+1}(a,0)=c_r,\qquad
H_{r+1}(a,b+1)=H_r(a,H_{r+1}(a,b)),
\qquad c_0=0,\quad c_r=1\ (r\geq1).
$$
The first three members are therefore \b[addition, multiplication and exponentiation]:
$$
\boxed{H_0(a,b)=a+b,\qquad H_1(a,b)=ab,\qquad H_2(a,b)=a^b.}
$$
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>, then
$$
g_r(a)=c_r,\qquad h_r(a,b,z)=H_r(a,z)
$$
are <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 \b[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), \b[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 predicate>
$$
B(x,t)=1\quad\Longleftrightarrow\quad
\text{that machine halts on input }x\text{ within }t\text{ steps}
$$
is <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> $\langle x,t\rangle$ with <primitive recursive> inverse coordinate functions. For example, the Cantor pairing function has inverses obtained by <bounded minimization>. Define
$$
f(\langle x,t\rangle)=
\begin{cases}x,&B(x,t)=1,\\x_0,&B(x,t)=0.\end{cases}
$$
The 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(\langle x,t\rangle)=x$. Thus
$$
\boxed{X\ne\varnothing\text{ and }X\text{ semidecidable}
\ \Longrightarrow\ \exists f\text{ primitive recursive with }\operatorname{ran}(f)=X.}
$$
The range need not be a <computable set>; deciding whether a value occurs anywhere in this total enumeration is an unbounded search.
Back to article page
