15-§. Структура примитино рекурсивных функций. Реализация алгоритма на машине Тьюринга

15-§. Структура примитино рекурсивных функций. Реализация алгоритма на машине Тьюринга.

1. 
   Структура примитино рекурсивных функций.
   

Определение 1.  Функция называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.
Гёдель впервые описал класс всех рекурсивных функций как класс всех числовых функций, определяемых в некоторой формальной системе. Черч в 1936 году пришел к тому же классу функций, исходя из других предпосылок.
Здесь построение класса вычислимых функций строится следующим образом.
Выбираются простейшие функции
(оператор сдвига),
(оператор аннулирования),
(оператор проектирования).
Далее вводятся операции над функциями.
Суперпозиция функций.
Рассмотрим функции

функцию и определяемую равенством

Будем говорить, что функция  получена из функций  и  суперпозицией.
Если мы каким-либо образом умеем вычислять функции   то функция  может быть вычислена так:
придадим переменным   некоторые значения  . 
Вычисляя все найдем
Вычисляя теперь найдем
Ясно, что если все функции   и  всюду определены, то функция  всюду определена.
Функция  будет не всюду определенной, если хотя бы одна из функций  не всюду определена, или если можно найти такие значения аргументов  , что  , но 
не определено
Таким образом, если функции  интуитивно вычислимы, то будет интуитивно вычислима и функция  .
Отметим, что возможны случаи, когда не все функции   зависят от всех п аргументов  . В этих случаях для получения суперпозиции используются фиктивные аргументы и функции   .
Например, функция

получается суперпозицией из функций и
.