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

Определение

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

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

${\displaystyle l(n),r(n)}$ - левый и правый члены пары с номером ${\displaystyle n}$ , ${\displaystyle rest(x,y)}$ - остаток от деления ${\displaystyle x}$ на ${\displaystyle y}$ .

Свойства

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

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

Примечания

Литература

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