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