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