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

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

Определение

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

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

$l(n),r(n)$ - левый и правый члены пары с номером $n$ Шаблон:Iw, $rest(x,y)$ - остаток от деления $x$ на $y$.

Свойства

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

$\mathrm{\Gamma }(x,0)=a_0,\mathrm{\Gamma }(x,1)=a_1,...,\mathrm{\Gamma }(x,n)=a_n$ имеет по меньшей мере одно решениеШаблон:Sfn.

Литература

• Шаблон:Книга