Изменения
→Вычислимые и частично рекурсивные функции
== Вычислимые и частично рекурсивные функции ==
{{Теорема
|statement= Множества [[Вычислимые функции|вычислимых ]] и частично рекурсивных функций совпадают.
|proof=
Программа вычисляющая частично рекурсивную функцию легко пишется на любом языке программирования. Поэтому нам достаточно показать что любая вычислимая функция примитивно рекурсивная. Функции <tex> IN </tex>, <tex> OUT </tex>, <tex> N </tex>, и как представляется состояние машины Тюринга описано в доказательстве [[Примитивно рекурсивные функции#Теорема о примитивной рекурсивности вычислимых функций|теоремы о примитивной рекурсивности вычислимых функций]].
