Русская Википедия:Функция Гёделя

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

Определение

Функцией Геделя <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.

Литература

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