Полнота по Тьюрингу

#любой_язык #теория

Как известно, большинство широко используемых языков программирования (особенно императивных)
полны по Тьюрингу. А некоторые — даже относительно времени компиляции, как, скажем,
С++ с их шаблонами.

А каким образом доказывается/опровергается полнота по Тьюрингу? Само по себе это
понятие  выглядит трудно формализуемым.
    

Ответы

Ответ 1

Формально это надо доказывать это с точки зрения теории рекурсивных функций — язык
полон по Тьюрингу тогда и только тогда, когда он позволяет записать каждую вычислимую
функцию. На практике для этого обычно достаточно ловко проапеллировать к [тезису Черча].(http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis)
См. также «How to Prove a Programming Language is Turing Complete?».


Ответ 2

Почему-то мне кажется, что если мы можем реализовать машину Тьюринга на каком-то
языке, то это означает, что он тьюринг-полный. Хотя могу ошибаться.