Kleene's T-predicate and output function

Fix the machine coding from A fixed effective binary encoding of deterministic one-tape Turing machines and the sequence coding from A natural-number coding of finite sequences.

For natural numbers $e,x,s$, define Kleene's $T$-predicate $T(e,x,s)$ to hold exactly when $s$ codes a finite sequence of configurations $C_0,\dots ,C_r$ such that:

• $e$ decodes to a machine $M$,
• $C_0$ is the initial configuration of $M$ on input $x$,
• $C_{j+1}$ is obtained from $C_j$ by the coded one-step update for every $j<r$, and
• $C_r$ is halting.

Define the output function $U(s)$ as follows. If $s$ decodes to a nonempty sequence whose final entry is a well-formed configuration code and the tape in that configuration contains a canonical binary numeral followed by blanks, let $U(s)$ be the natural number represented by that numeral. On every other input, set $U(s)=0$. Thus $U$ only extracts data from the final coded configuration; it does not first test an unbounded existential claim about whether some machine and input have that history. The output-word convention is the one fixed in Finite computation histories, halting computations, and divergence.

Define the numeric zero-test for $T$ by ${\tau }_T(e,x,s):=\{\begin{array}{ll}0,& T(e,x,s),\\ 1,& \text{otherwise}\mathrm{.}\end{array}$

The primitive-recursive readers of The sequence-length and coordinate-reading functions are primitive recursive parse the history and every configuration coordinate. A bounded universal check over the decoded list verifies the initial configuration, each update using The one-step update on coded Turing configurations is primitive recursive, and the final halting state. Equality tests, composition, bounded search, and bounded universal quantification preserve primitive recursiveness by Basic arithmetic operations and bounded quantification are primitive recursive. The same readers locate the final configuration and perform a bounded scan of its finitely encoded tape segment, checking and evaluating the canonical binary numeral. Consequently the combined history-validity zero-test ${\tau }_T$ and the final-output reader $U$ are primitive recursive, and $T$ is a primitive-recursive relation through its zero-test.

• $T(e,x,s)$ says that $s$ is a complete halting computation history, not just one legal step.

• The least $s$ satisfying $T(e,x,s)$ is the first successful coded history in the usual numeric order, not necessarily the shortest history.