Функция Гёделя (Srutenx I~;ylx)
Перейти к навигации
Перейти к поиску
Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел.
Определение[править | править код]
Функцией Геделя называется выражение[1]:
- , где
- левый и правый члены пары с номером канторовского перечисления пар натуральных чисел , - остаток от деления на .
Свойства[править | править код]
- Функция Геделя примитивно рекурсивна.
- Какова бы ни была конечная последовательность натуральных чисел , система уравнений
имеет по меньшей мере одно решение[2].
Примечания[править | править код]
- ↑ Алгоритмы и рекурсивные функции, 1986, с. 62.
- ↑ Алгоритмы и рекурсивные функции, 1986, с. 62-64.
Литература[править | править код]
- Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 367 с. — 10 400 экз.