Изменения

|statement= Если для вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любого входа любых аргументов <tex> x args </tex> максимальное количество за которое будет посчитана <tex> F(x) </tex> на [[MT |Машина Тюринга]] равно <tex> T(xargs) </tex>, то <tex> F </tex> примитивно рекурсивная функция.

 <tex> L </tex> - состояние MT слева от головки ленты, представлено в виде числа в системы счисления с основанием равным алфавиту MT, число . о записано слева направо. Пробелу соответствует ноль, чтобы число было конечным. 

 Тогда всем переходам соответствует функция <tex> f ([L,R,S,C]) </tex> принимающая состояние МТ и возвращающая новое состояние.Покажем что она примитивно рекурсивная . При применении перехода в <tex> C </tex> записывается новый символ,затем из-за сдвига головки а в <tex> L </tex> и <tex> R </tex>, в конец добавляется новая цифра или удаляется старая, затем в <tex> C </tex> записываетcя символ после сдвига, и в конце перехода в <tex> S </tex> записывается новое состояние автомата. Операции добавления в конец цифры или удаления последней цифры легко выражаются через деление и умноженияпростые арифметические операции, следовательно они примитивно рекурсивные. Все остальные операции являются простыми операциями над списками, а значит они тоже примитивно рекурсивные. Из этого следует что применения перехода {{---}} примитивно рекурсивная функция. В силу того что нужный переход можно выбрать используя конечное число функций if следует что и <tex> f </tex> тоже также является примитивно рекурсивной функцией.Функции преобразование аргументов в формат входных данных для МТ и получения ответа по состоянию МТ также выражаются через простые арифметические операции а значит они примитивно рекурсивные. Назовем их IN и OUT.Рассмотрим функцию двух аргументов <tex> N([L,R,S,C],t) </tex> которая принимает состояние MT , число шагов <tex> t </tex> и возвращает состояние MT после <tex> t </tex> шагов.Покажем что N - примитивно рекурсивная функция.<tex> N([L,R,S,C],t) = [L,R,S,C] </tex><tex> N([L,R,S,C],t+1) = h([L,R,S,C],t+1,N([L,R,S,C],t)) </tex> , где h([L,R,S,X],y,[L1,R1,S1,C1]) = f([L1,R1,S1,C1]) </tex>Подставим вместо <tex> t </tex> T(args) и в итоге получим что F(args) = OUT(N(IN(args),T(args))) - примитивно рекурсивная функция. }}