Kleene's Normal Form Theorem

Statement

There is a total computable function $U:\mathbb{N}\to \mathbb{N}$ and for each $n:{\mathbb{N}}_{\ge 1}$ a decidable predicate $T_n(e,x,z)$ such that:

• ${\varphi }_e^{(n)}(x)$ is defined iff $\exists z.T_n(e,x,z)$
• ${\varphi }_e^{(n)}(x)\simeq U(\mu z.T_n(e,x,z)$

See also

Universal program

References

cutland1980-computability