Complete numbering

In computability theory complete numberings are generalizations of Gödel numbering first introduced by A.I. Mal'tsev in 1963. They are studied because several important results like the Kleene's recursion theorem and Rice's theorem, which were originally proven for the Gödel-numbered set of computable functions, still hold for arbitrary sets with complete numberings.

Definition

A numbering $\nu$ of a set $A$ is called complete (with respect to an element $a \in A$ ) if for every partial computable function $f$ there exists a total computable function $h$ so that

\nu \circ h(i) = \left\{ \begin{matrix} \nu \circ f(i) &\mbox{if}\ i \in \mathrm{dom}(f), \\ a &\mbox{otherwise}. \end{matrix} \right.

The numbering $\nu$ is called precomplete if

\nu \circ f(i) = \nu \circ h(i) \qquad i \in \mathrm{dom}(f).\,

Examples

any numbering of a singleton set is complete
the identity function on the natural numbers is not complete
a Gödel numbering is precomplete

References

A.I. Mal'tsev, Sets with complete numberings. Algebra i Logika, 1963, vol. 2, no. 2, 4-29 (Russian)

This article is issued from Wikipedia - version of the 12/2/2012. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.