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

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

Определение

Функцией Геделя Γ(x,y) называется выражение: Γ(x,y)=rest(l(x),1+(y+1)r(x)) , где l(n),r(n) - левый и правый член пары канторовского перечисления пар натуральных чисел, rest(x,y) - остаток от деления x на y.

Свойства


  • Функция Геделя примитивно рекурсивна.
  • Каково бы ни была конечная последовательность натуральных чисел a0,a1,...,an, система уравнений
Γ(x,0)=a0,Γ(x,1)=a1,...,Γ(x,n)=an имеет по меньшей мере одно решение.