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

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

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

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