Kleene's T predicate

Summary

Kleene's T predicate is a primitive recursive relation $T(e, x, c)$ about computations. It says that $c$ codes a halting computation of the program with index $e$ on input $x$. Together with a primitive recursive function $U$ that reads off the output, it gives Kleene's normal form theorem. Every partial computable function has the form $x \mapsto U(\mu c \, T(e, x, c))$ for some $e$. So a single unbounded search is enough for any computation.