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 ex ...

, 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 considered to be examples of a primary key In the relational model ...

(enumeration) of the set of all uniformly recursively enumerable sets that has no repetitions: each recursively enumerable set appears exactly once in the enumeration (Vereščagin and Shen 2003:30). The existence of such numberings was established by Richard M. Friedberg in 1958 (Cutland 1980:78).

References

* Nigel Cutland (1980), ''Computability: An Introduction to Recursive Function Theory'', Cambridge University Press. . * Richard M. Friedberg (1958), ''Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication'', ''Journal of Symbolic Logic'' 23:3, pp. 309–316. * Nikolaj K. Vereščagin and A. Shen (2003), ''Computable Functions'', American Mathematical Soc.

External links

Institute of Mathematics
Computability theory {{Mathlogic-stub