Нумерация Фридберга - Friedberg numbering

В теория вычислимости, а Нумерация Фридберга это нумерация (перечисление) множества всех равномерно рекурсивно перечислимые множества не имеет повторений: каждое рекурсивно перечислимое множество появляется в перечислении ровно один раз (Верещагин и Шен 2003: 30).

Существование такой нумерации было установлено Ричард М. Фридберг в 1958 г. (Катленд 1980: 78).

использованная литература

  • Найджел Катленд (1980), Вычислимость: введение в теорию рекурсивных функций, Издательство Кембриджского университета. ISBN  9780521294652.
  • Ричард М. Фридберг (1958), Три теоремы о рекурсивном перечислении. I. Разложение. II. Максимальный набор. III. Перечисление без дублирования, Журнал символической логики 23: 3, стр. 309–316.
  • Николай К. Верещагин и А. Шен (2003), Вычислимые функции, American Mathematical Soc.

внешние ссылки