Функция Гёделя (Srutenx I~;ylx)

Перейти к навигации Перейти к поиску

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

Определение

[править | править код]

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

, где

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

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

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

Примечания

[править | править код]

Литература

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