Доказательство.

Пусть произв-е ф-ии от n переменных.

Рассмотрим произвольный набор .

Тогда будут определены в этом наборе в силу свойства всюду определенности.

Функция g будет определена на наборе , в силу свойства всюду определенности, а по определению подстановки это и есть функция f.

Таким образом, мы доказали, что функция f определена на наборе .

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

2⁰. Операция подстановки сохраняет свойство алгоритмической вычислимости функций:

если функции и алгоритмически вычислимы, и

f=S(g,, , то существует алгоритм A_f, вычисляющий функцию f.

Доказательство. Пусть задан произвольный набор . Это означает, что этот набор , где i=1,…,m. Далее поступаем следующим образом:

1 шаг: применяем к набору алгоритм , вычисляющий функцию . Так как функция по условию алгоритмически вычислимая функция, то за конечное число шагов алгоритм дает конечный результат для функции .

2 шаг: применяем к набору алгоритм , вычисляющий функцию . Так как функция по условию алгоритмически вычислимая функция, то через конечное число шагов работа алгоритма завершается результативно, т.е. будут вычислено значение функция на наборе и т.д. Если работа всех алгоритмов на наборе завершилась результативно, т.е. вычислены соответствующие значения , на следующий шаг, т.е.

m+1–шаг:применяем алгоритм , вычисляющий функцию g, к набору . В силу свойства алгоритмически вычислимости функцию g, через конечное число шагов алгоритм завершает работу на наборе результативно, и этот результат будем считать значением функции f, так как по определению операции подстановки

f .

В случае, когда алгоритм где i=1,…,m не останавливается или завершает работу нерезультативно, будем считать, что искомый алгоритм для вычисления данной функции, т.е. функции f , не существует.