= Solution
The <partial recursive function>[partial recursive functions] form the smallest class containing the <zero function>, <successor function>, and <projection function>[projection functions] and closed under <function composition in recursion theory>[composition], <primitive recursion>, and <unbounded minimization>.
Fix a <register machine> $P$ with $k$ inputs. By the permitted result, its complete configuration after $t$ steps,
$$
S(\mathbf x,t),
$$
is a <total computable function>[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 function
$$
\tau(\mathbf x)=\mu t\,[H(\mathbf x,t)],
$$
where <unbounded minimization> is undefined when no halting time exists. Extracting the output register from a configuration is recursive, so
$$
f(\mathbf x)=\operatorname{out}(S(\mathbf x,\tau(\mathbf x)))
$$
is partial recursive. Hence every <partial computable function> is partial recursive.
Back to article page
