192
правки
Изменения
Нет описания правки
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.
На практике полнота по Тьюрингу — идеализация. Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времени, прежде чем их выключат.
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.
===Тьюринг-полнота и неполнота некоторых языков программирования===
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
{| style="background-color:#CCC;margin:0.5px"
!style="background-color:#EEE;padding:2px 8px"| '''Название языка'''
!style="background-color:#EEE;padding:2px 8px"| '''Год изобретения'''
!style="background-color:#EEE;padding:2px 8px"| '''Парадигма'''
!style="background-color:#EEE;padding:2px 8px"| '''Уровень'''
!style="background-color:#EEE;padding:2px 8px"| '''Машинно-зависимость'''
!style="background-color:#EEE;padding:2px 8px"| '''Полнота по Тьюрингу'''
|-
|style="background-color:#FFF;padding:2px 8px"| C
|style="background-color:#FFF;padding:2px 8px"| 1972
|style="background-color:#FFF;padding:2px 8px"| Процедурный
|style="background-color:#FFF;padding:2px 8px"| Низкий
|style="background-color:#FFF;padding:2px 8px"| зав. от ISO
|style="background-color:#FFF;padding:2px 8px"| Да
|-
|style="background-color:#FFF;padding:2px 8px"| C++
|style="background-color:#FFF;padding:2px 8px"| 1983
|style="background-color:#FFF;padding:2px 8px"| Мультипарадигменный
|style="background-color:#FFF;padding:2px 8px"| Высокий/Низкий
|style="background-color:#FFF;padding:2px 8px"| Нет
|style="background-color:#FFF;padding:2px 8px"| Да
|}
===Тьюринговская трясина===
* [http://cmcmsu.no-ip.info/download/alg.lang.completeness.pdf А. А. Вылиток. Об алгоритмической полноте некоторых языков программирования]
* [https://ethclassic.ru/2016/10/21/turing-completeness-reality/ «Умные контракты»: полнота по Тьюрингу и реальность]
