Computable Denumeration

Definition

A computable denumeration of the $n$-ary partial computable functions is an effective listing $({\varphi }_e^{(n)}{)}_{e\in \mathbb{N}}$ such that there is a single partial computable function

$$U^{(n+1)}:{\mathbb{N}}^{n+1}\rightharpoonup \mathbb{N}$$

with

$$U^{(n+1)}(e,x_1,\dots ,x_n)\simeq {\varphi }_e^{(n)}(x_1,\dots ,x_n)$$

for every index $e$ and all inputs $x_1,\dots ,x_n:\mathbb{N}$.

In other words, the family $({\varphi }_e^{(n)}{)}_{e\in \mathbb{N}}$ is a numbering of the $n$-ary partial computable functions for which evaluation from an index is itself computable.

Godel encodings are essentially the same thing, but they drop the requirement that there is a unique partial function for each code. Godel encodings are syntactic in nature, whereas computable denumeration is semantic: Acting on partial functions, and forgetting how they were constructed.

Remarks

Such a denumeration assigns to each program code or index $e$ the partial computable function computed by that code. The associated function $U$ is a universal program.

Computable denumerations are used in the statements of the $S_n^m$-theorem, and other basic results of computability theory.

Related Concepts

Partial Computable Function
Smn Theorem
Universal program
Computable Denumeration

References

cutland1980-computability