313
правок
Изменения
→Теорема о примитивной рекурсивности вычислимых функций
Рассмотрим функцию двух аргументов <tex> \mathrm{N}([L,R,S,C],t) </tex> которая принимает состояние [[Машина Тьюринга|МТ]] , число шагов <tex> t </tex> и возвращает состояние [[Машина Тьюринга|МТ]] после <tex> t </tex> шагов.
Покажем что <tex>\mathrm{N}</tex> {{- --}} примитивно рекурсивная функция.
<tex> \mathrm{N}([L,R,S,C],t) = [L,R,S,C] </tex>
