WikiSort.ru - Не сортированное

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

Определение

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

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

${\displaystyle l(n),r(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}}$ имеет по меньшей мере одно решение^[2].

Примечания

Литература

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