Friedberg numbering

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computability theory, a Friedberg numbering is a numbering (enumeration) of the set of all partial recursive functions that has no repetitions: each partial recursive function 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[edit]

  • Nigel Cutland (1980), Computability: An Introduction to Recursive Function Theory, Cambridge University Press. ISBN 9780521294652.
  • 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[edit]