Русская Википедия:Функция Гёделя
Материал из Онлайн справочника
Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел.
Определение
Функцией Геделя <math>\Gamma (x, y)</math> называется выражениеШаблон:Sfn:
- <math>\Gamma (x, y) = rest(l(x), 1+(y+1)r(x))</math> , где
<math>l(n), r(n)</math> - левый и правый члены пары с номером <math>n</math> Шаблон:Iw, <math>rest(x, y)</math> - остаток от деления <math>x</math> на <math> y</math>.
Свойства
- Функция Геделя примитивно рекурсивна.
- Какова бы ни была конечная последовательность натуральных чисел <math>a_{0}, a_{1}, ..., a_{n}</math>, система уравнений
<math>\Gamma(x,0)=a_{0}, \Gamma(x,1)=a_{1}, ..., \Gamma(x,n)=a_{n}</math> имеет по меньшей мере одно решениеШаблон:Sfn.
Примечания
Литература
