= Program index
{title2=$e,\varphi_e$}
A program index is a <natural number> encoding a program in a fixed effective enumeration of programs, often written $(\varphi_e)_{e\in\mathbb N}$ for the corresponding partial <computable functions>. The meaning of an index depends on the chosen programming model and enumeration; $\varphi_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)=\varphi_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 $\varphi_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.
Back to article page
