Функция Гёделя
Функция Геделя — функция, применяющаяся в теории алгоритмов для облегчения нумерации множеств натуральных чисел.
Определение
Функцией Геделя называется выражение[1]:
- , где
- левый и правый член пары канторовского перечисления пар натуральных чисел, - остаток от деления на .
Свойства
- Функция Геделя примитивно рекурсивна.
- Какова бы ни была конечная последовательность натуральных чисел , система уравнений
имеет по меньшей мере одно решение[2].
Примечания
- Алгоритмы и рекурсивные функции, 1986, с. 62.
- Алгоритмы и рекурсивные функции, 1986, с. 62-64.
Литература
- Мальцев А. И. Алгоритмы и рекурсивные функции. — М.: Наука, 1986. — 367 с. — 10 400 экз.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.