Изменения
→Теорема о примитивной рекурсивности вычислимых функций
== Теорема о примитивной рекурсивности вычислимых функций ==
{{Теорема
|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>, где:
