Нумерация вычислимых функций

Определение 5.1. Пусть f – n-местная функция, вычислимая по программе P с геделевым номером m = g(P). Число m будем называть индексом функции f. Вычислимую функцию от n переменных с индексом m будем обозначать символом .

Из определения 5.1 следует, что каждая n-местная вычислимая функция f представлена в перечислении

Ниже мы в основном будем рассматривать одноместные вычислимые функции . Для простоты в их обозначении верхний индекс будем опускать.