Тьюринг-полнота — различия между версиями
Romanosov (обсуждение | вклад) |
Romanosov (обсуждение | вклад) |
||
| Строка 4: | Строка 4: | ||
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными. | Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными. | ||
| + | |||
| + | Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах. | ||
| + | |||
| + | На практике полнота по Тьюрингу — идеализация. Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времени, прежде чем их выключат. | ||
| Строка 28: | Строка 32: | ||
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным. | * Поддержка входных и выходных данных (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"| Да | ||
| + | |||
| + | |} | ||
===Тьюринговская трясина=== | ===Тьюринговская трясина=== | ||
| Строка 51: | Строка 79: | ||
* [http://cmcmsu.no-ip.info/download/alg.lang.completeness.pdf А. А. Вылиток. Об алгоритмической полноте некоторых языков программирования] | * [http://cmcmsu.no-ip.info/download/alg.lang.completeness.pdf А. А. Вылиток. Об алгоритмической полноте некоторых языков программирования] | ||
| + | |||
| + | * [https://ethclassic.ru/2016/10/21/turing-completeness-reality/ «Умные контракты»: полнота по Тьюрингу и реальность] | ||
Версия 18:34, 7 января 2017
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.
На практике полнота по Тьюрингу — идеализация. Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времени, прежде чем их выключат.
Содержание
Критерии Тьюринг-полноты
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
- Конечность (нет бесконечных символьных множеств и пр.)
- Фиксированное описание
- Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".
- Неограниченность времени выполнения
- Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
- Циклы while с прерыванием или им эквивалентные
- Возможность останавливать выполнение или каким-то образом подавать сигнал о результатах выполнения
- Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
- Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.
Тьюринг-полнота и неполнота некоторых языков программирования
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
| Название языка | Год изобретения | Парадигма | Уровень | Машинно-зависимость | Полнота по Тьюрингу |
|---|---|---|---|---|---|
| C | 1972 | Процедурный | Низкий | зав. от ISO | Да |
| C++ | 1983 | Мультипарадигменный | Высокий/Низкий | Нет | Да |
Тьюринговская трясина
Тьюринговская трясина — жаргонное общее название для языков программирования, которые Тьюринг-полны, но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики. Многие эзотерические языки программирования также являются «трясинами Тьюринга».
