Функция Гёделя

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

Определение

править

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

  , где

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

Свойства

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

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

Примечания

править

Литература

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