Открыть главное меню

Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел.

ОпределениеПравить

Функцией Геделя   называется выражение[1]:

  , где

  - левый и правый член пары канторовского перечисления пар натуральных чисел,   - остаток от деления   на  .

СвойстваПравить

  • Функция Геделя примитивно рекурсивна.
  • Каково бы ни была конечная последовательность натуральных чисел  , система уравнений

  имеет по меньшей мере одно решение[2].

ПримечанияПравить

ЛитератураПравить

  • Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 367 с. — 10 400 экз.