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

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

Определение

Функцией Геделя $\Gamma (x,y)$ называется выражение:

$\Gamma (x,y)=rest(l(x),1+(y+1)r(x))$ , где

$l(n),r(n)$ - левый и правый члены пары с номером $n$ канторовского перечисления пар натуральных чисел, $rest(x,y)$ - остаток от деления $x$ на $y$.

Свойства

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

$\Gamma (x,0)=a_{0},\Gamma (x,1)=a_{1},...,\Gamma (x,n)=a_{n}$ имеет по меньшей мере одно решение.

Литература

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