Предложение.(свойства операций суперпозиции и примитивной рекурсии)

Операции суперпозиции и примитивной рекурсии сохраняют:

1. всюду определённость функций;

2. интуитивную вычислимость функций.

Доказательство проведем для операции суперпозиции. Пусть m -арная функция получена в результате операции суперпозиции из функций и .

1. Если все функции и – всюду определённые, то функция всюду определена. Функция будет не всюду определённой, если одна из функций не всюду определена или если можно найти такие , что , , , но значение неопределено.

2. Если каким-либо образом можно вычислять значения функций и , то ясно, как можно вычислить значение функции . Придадим переменным некоторые значения . Вычислим все , . Получим значения , , . Вычисляя теперь , получим, что . Таким образом, если функции и интуитивно вычислимы, то и функция интуитивно вычислима.

Предложение доказано.

Функция f называется примитивно рекурсивной (п.р.ф.), если ее можно получить из простейших функций с помощью конечного числа операций суперпозиции и примитивной рекурсии.

Свойства примитивно рекурсивных функций характеризует следующее