Изменения
→Теорема о примитивной рекурсивности вычислимых функций
== Теорема о примитивной рекурсивности вычислимых функций ==
{{Теорема
|statement= Если для вычислимой функции <tex> F </tex> существует примитивно рекурсивная функция <tex> T </tex>, такая что для любых аргументов <tex> args </tex> максимальное количество за которое будет посчитана <tex> F(x) </tex> на [[MT|Машина Тюринга|МТ]] равно <tex> T(args) </tex>, то <tex> F </tex> примитивно рекурсивная функция.
|proof=
Каждому состоянию MT поставим в соответствие список из четырех чисел [L,R,S,C],где
Тогда всем переходам соответствует функция <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> также является примитивно рекурсивной функцией. Функции преобразование аргументов в формат входных данных для МТ и получения ответа по состоянию МТ также выражаются через простые арифметические операции а значит они примитивно рекурсивные. Назовем их <tex> IN </tex> и <tex> OUT</tex>.
Рассмотрим функцию двух аргументов <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>
}}
