Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел.
Определение Функцией Геделя называется выражение:
, где
— левый и правый члены пары с номером , — остаток от деления на .
Свойства Функция Геделя примитивно рекурсивна. Какова бы ни была конечная последовательность натуральных чисел , система уравнений имеет по меньшей мере одно решение.
Примечания
Литература
Категория:Теория алгоритмов Геделя