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

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

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

…

…

.

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

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

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

Дата добавления: 2014-12-29