12.1. Вычислимость суперпозиции

Теорема 12.3. Пусть функции , , …, вычислимы на МПД. Тогда вычислима и функция .

Доказательство. Пусть  — программы стандартного вида для вычисления функций , , …, соответственно. Напишем программу Н для вычисления H. Положим . Запомним в регистрах , в регистрах запоминаем значения , …,  соответственно. Указанные регистры не затрагиваются вычислениями по программам . Теперь дадим программу Р вычисления H:

…

…

.

Ясно: вычисление останавливается тогда и только тогда, когда заканчиваются вычисления каждой , и вычисление , что и требовалось доказать.

Следствие 12.4. Пусть  — вычислимая на МПД функция и  — последовательность N переменных из (возможно с повторениями). Тогда функция вычислима.

Доказательство. Если , то , и потому функция H — вычислима, что и требовалось доказать.

< Предыдущая		Следующая >