Тьюринг-полнота
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.
| Определение: |
| Вычислительное устройство является Тьюринг-эквивалентным, если оно может эмулировать машину Тьюринга. |
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
В теории вычислимости исполнитель (множество вычисляющих элементов) называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.
На практике полнота по Тьюрингу — идеализация. Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времени, прежде чем их выключат.
Критерии Тьюринг-полноты
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
- Конечность (нет бесконечных символьных множеств и пр.)
- Фиксированное описание
- Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".
- Неограниченность времени выполнения
- Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
- Циклы while с прерыванием или эквивалентные им
- Возможность останавливать выполнение (halt) или каким-то образом подавать сигнал о результатах выполнения
- Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
- Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.
Тьюринг-полнота и неполнота некоторых языков программирования
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
Assembly language
Язык Ассемблера сильно ограничен: он рассчитан на архитектуру с конечной памятью и работает с конечным набором регистров. Однако, не был бы он полным по Тьюрингу, не были бы Тьюринг-полны и другие языки программирования.
Всё необходимое для машины Тьюринга на asm можно сделать примерно так:
ADDS r0, r0, #1 ; сдвиг ленты вправо ADDS r0, r0, #-1 ; сдвиг ленты влево ADDS [r0], [r0], #1 ; инкремент значения, на которое "указывает" головка ленты ADDS [r0], [r0], #-1 ; декремент значения, на которое "указывает" головка ленты
И далее использовать инструкцию BEQ или ей подобную, чтобы выполнять определённую последовательность команд при определённом текущем значении, таким образом обеспечив ветвление.
Pascal
Язык Pascal позволяет смоделировать ленту машины Тьюринга с помощью двунаправленного списка из переменных, создаваемых оператором new, семантика которого не предполагает отказа в создании переменной. Также с помощью списков можно смоделировать сколь угодно большие числа. Стандарт не накладывает никаких ограничений: указательный тип абстрактен, множество значений указательного типа языком не ограничено. В Паскале есть еще один тип данных с неограниченным множеством значений, файловый, также пригодный для моделирования ленты машины Тьюринга и представления больших чисел. Достаточно утверждений для очевидности Тьюринг-полноты языка Pascal.
C
SQL
Сам по себе SQL не считается полным по Тьюрингу языком. Однако, у него существует множество расширений, позволяющих делать рекурсивные запросы, циклы, списки, деревья и пр. Например, реализация решений некоторых известных задач с помощью PostgreSQL 8.4. Тем не менее, всё ещё остаётся ограниченное query execution time.
HTML
HTML можно назвать языком программирования только в контексте формальной полемики. На деле он является языком гипертекстовой разметки и ни чем больше. Т. е. на HTML можно совершить только некоторую ограниченную совокупность действий, интерпретируемых браузером, однако никто не запрещает сделать язык, идентичный по синтаксису с HTML, но интерпретируемый совершенно по другому таким образом, чтобы он был полным по Тьюрингу.
Некоторые другие ЯП
| Название языка | Год изобретения | Парадигма | Уровень | Машинно-зависимость | Полнота по Тьюрингу |
|---|---|---|---|---|---|
| C | 1972 | Процедурный | Низкий | зав. от ISO | Да |
| C++ | 1983 | Мультипарадигменный | Высокий/Низкий | Нет | Да |
| Язык Ассемблера | 1950 | Полнофункциональный | Низкий | Да | Да |
| SQL | 1989 | Декларативный | Высокий | Нет | Нет |
| Haskell | 1990 | Функциональный | Высокий | Нет | Да |
| HTML | 1986 | Декларативный | Высокий | Нет | Нет |
| CSS | 1996 | Декларативный | Высокий | Нет | Нет |
| Java | 1965 | Объектно-ориентированный | Высокий | Нет | Да |
Интересные случаи полноты по Тьюрингу
Шаблоны C++
Шаблоны C++ позволяют производить сложные вычисления ещё на стадии компиляции программы. Впервые это было продемонстрировано Эрвином Унрухом, который реализовал рекурсивный алгоритм распознавания простых чисел в процессе компиляции. Позже в статье Университета Индиана было продемонстрировано кодирование машины Тьюринга в шаблонах C++.
Java Generics
Аналогично C++ Templates, Generics, несмотря на свои отличия, тоже оказались полными по Тьюрингу, что было подтверждено Раду Григор в статье Кентского Университета.
mov
Утилита M/o/Vfuscator превращает любую программу на языке C в огромную последовательность из инструкций mov.
HTML5 + CSS3
Нововведения новых версий HTML/CSS позволяют построить правило 110, которое является Тьюринг-полным.
Minecraft
Little Big Planet
Super Mario World
Braid
Excel
Тьюринговская трясина
Тьюринговская трясина — жаргонное общее название для языков программирования, которые Тьюринг-полны, но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики.
Первыми представителями "трясины" были лямбда-исчисление, комбинаторная логика и сама машина Тьюринга.
Многие эзотерические языки программирования также являются «трясинами Тьюринга» (напр. Brainfuck, Spoon, Malbolge, Whitespace).
