Тьюринг-полнота
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.
На практике полнота по Тьюрингу — идеализация. Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времени, прежде чем их выключат.
Критерии Тьюринг-полноты
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
- Конечность (нет бесконечных символьных множеств и пр.)
- Фиксированное описание
- Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".
- Неограниченность времени выполнения
- Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
- Циклы while с прерыванием или им эквивалентные
- Возможность останавливать выполнение или каким-то образом подавать сигнал о результатах выполнения
- Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
- Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.
Тьюринг-полнота и неполнота некоторых языков программирования
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
| Название языка | Год изобретения | Парадигма | Уровень | Машинно-зависимость | Полнота по Тьюрингу |
|---|---|---|---|---|---|
| C | 1972 | Процедурный | Низкий | зав. от ISO | Да |
| C++ | 1983 | Мультипарадигменный | Высокий/Низкий | Нет | Да |
Тьюринговская трясина
Тьюринговская трясина — жаргонное общее название для языков программирования, которые Тьюринг-полны, но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики. Многие эзотерические языки программирования также являются «трясинами Тьюринга».
