 Program index

A program index is a natural number encoding a program in a fixed effective enumeration of programs, often written $({\phi }_e{)}_{e\in \mathbb{N}}$ for the corresponding partial computable functions. The meaning of an index depends on the chosen programming model and enumeration; ${\phi }_e(x)$ may be undefined because program $e$ does not halt on input $x$.

The universal partial computable function simulates the indexed program: $U(e,x)={\phi }_e(x)$ whenever that computation halts. Two different indices can compute the same partial function, because different program texts can implement identical behavior. Equality of indices is therefore a syntactic test, whereas equality of computed functions is a semantic property.

The halting problem becomes the question whether ${\phi }_e(x)$ is defined. Encoding programs as numbers also permits diagonal arguments, such as constructing a computation that uses its own index as input. These arguments concern a specified effective enumeration, rather than assuming every sequence of functions can be uniformly simulated.