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