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

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

Определение

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

Γ ( x , y ) = r e s t ( l ( x ) , 1 + ( y + 1 ) r ( x ) ) {displaystyle Gamma (x,y)=rest(l(x),1+(y+1)r(x))} , где

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

Свойства

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

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