In
computability theory
Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...
, admissible numberings are enumerations (
numberings) of the set of
partial computable function
Computable functions are the basic objects of study in computability theory. Computable functions are the formalized analogue of the intuitive notion of algorithms, in the sense that a function is computable if there exists an algorithm that can do ...
s that can be converted ''to and from'' the standard numbering. These numberings are also called acceptable numberings and acceptable programming systems.
Rogers' equivalence theorem shows that all acceptable programming systems are equivalent to each other in the formal sense of numbering theory.
Definition
The formalization of computability theory by
Kleene
Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...
led to a particular universal partial computable function Ψ(''e'', ''x'') defined using the
T predicate. This function is universal in the sense that it is partial computable, and for any partial computable function ''f'' there is an ''e'' such that, for all ''x'', ''f''(''x'') = Ψ(''e'',''x''), where the equality means that either both sides are undefined or both are defined and are equal. It is common to write ψ
''e''(''x'') for Ψ(''e'',''x''); thus the sequence ψ
0, ψ
1, ... is an enumeration of all partial computable functions. Such enumerations are formally called computable numberings of the partial computable functions.
An arbitrary numbering η of partial functions is defined to be an ''admissible numbering'' if:
* The function ''H''(''e'',''x'') = η
''e''(''x'') is a partial computable function.
* There is a total computable function ''f'' such that, for all ''e'', η
''e'' = ψ
''f''(''e'').
* There is a total computable function ''g'' such that, for all ''e'', ψ
''e'' = η
''g''(''e'').
Here, the first bullet requires the numbering to be computable; the second requires that any index for the numbering η can be converted effectively to an index to the numbering ψ; and the third requires that any index for the numbering ψ can be effectively converted to an index for the numbering η.
Rogers' equivalence theorem
Hartley Rogers, Jr. Hartley Rogers Jr. (July 6, 1926 – July 17, 2015) was a mathematician who worked in computability theory, and was a professor in the Mathematics Department of the Massachusetts Institute of Technology.
Biography
Born in 1926 in Buffalo, New York ...
showed that a numbering η of the partial computable functions is admissible if and only if there is a total computable bijection ''p'' such that, for all ''e'', η
''e'' = ψ
''p''(''e'') (Soare 1987:25).
See also
*
Friedberg numbering In computability theory, a Friedberg numbering is a numbering
There are many different numbering schemes for assigning nominal numbers to entities. These generally require an agreed set of rules, or a central coordinator. The schemes can be consid ...
References
*
Y.L. Ershov (1999), "Theory of numberings", ''Handbook of Computability Theory'', E.R. Griffor (ed.), Elsevier, pp. 473–506.
* M. Machtey and P. Young (1978), ''An introduction to the general theory of algorithms'', North-Holland, 1978.
* H. Rogers, Jr. (1967), ''The Theory of Recursive Functions and Effective Computability'', second edition 1987, MIT Press. (paperback),
*
R. Soare (1987), ''Recursively enumerable sets and degrees'', Perspectives in Mathematical Logic, Springer-Verlag. {{ISBN, 3-540-15299-7
Theory of computation
Computability theory