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

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

Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.

Критерии Тьюринг-полноты

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

• Конечность (нет бесконечных символьных множеств и пр.)

• Фиксированное описание

• Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".

• Неограниченность времени выполнения

• Возможность функциональной композиции (вызов одной функции из другой, рекурсия)

• Циклы while с прерыванием или им эквивалентные

• Возможность останавливать выполнение или каким-то образом подавать сигнал о результатах выполнения

• Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.

• Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.

Тьюринг-полнота некоторых языков программирования

Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.

Тьюринговская трясина

Тьюринговская трясина — жаргонное общее название для языков программирования, которые Тьюринг-полны, но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики. Многие эзотерические языки программирования также являются «трясинами Тьюринга».

Источники информации

• Cunningham & Cunningham, Inc. — Turing Complete

• Stackexchange — What makes a language Turing-complete?

• Википедия — Тьюринговская трясина

• Википедия — Полнота по Тьюрингу

• А. А. Вылиток. Об алгоритмической полноте некоторых языков программирования