192
правки
Изменения
Нет описания правки
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.
Вычислительное устройство является Тьюринг-эквивалентным, если оно может эмулировать машину Тьюринга.
В теории вычислимости исполнитель (множество вычисляющих элементов) называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
* Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
* Циклы while с прерыванием или эквивалентные им эквивалентные
* Возможность останавливать выполнение (halt) или каким-то образом подавать сигнал о результатах выполнения
* Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 фиксированного n бит данных и возвращает не более 5 n бит, этот язык не может быть Тьюринг-полным.
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
===Assembly language===
===Pascal===
===C===
===SQL===
===HTML===
Мы можем назвать HTML языком программирования только в контексте формальной полемики. На деле он является языком гипертекстовой разметки и ни чем больше. Но читатель должен понимать, что если нет четко прописанных стандартов, то никто не запрещает сделать язык, идентичный по синтаксису с HTML, но интерпретируемый совершенно по другому таким образом, чтобы он был полным по Тьюрингу.
===Некоторые другие ЯП===
{| style="background-color:#CCC;margin:0.5px"
|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"| 1950
|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"| Да
|-
|style="background-color:#FFF;padding:2px 8px"| SQL
|style="background-color:#FFF;padding:2px 8px"| 1989
|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"| Нет
|-
|style="background-color:#FFF;padding:2px 8px"| Haskell
|style="background-color:#FFF;padding:2px 8px"| 1990
|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"| Да
|-
|style="background-color:#FFF;padding:2px 8px"| HTML
|style="background-color:#FFF;padding:2px 8px"| 1986
|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"| Нет
|-
|style="background-color:#FFF;padding:2px 8px"| CSS
|style="background-color:#FFF;padding:2px 8px"| 1996
|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"| Нет
|-
|style="background-color:#FFF;padding:2px 8px"| Java
|style="background-color:#FFF;padding:2px 8px"| 1965
|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"| Да
|}
==Интересные случаи полноты по Тьюрингу==
===Шаблоны C++===
Шаблоны C++ позволяют производить сложные вычисления ещё на стадии компиляции программы. Впервые это было продемонстрировано Эрвином Унрухом, который реализовал рекурсивный алгоритм распознавания простых чисел в процессе компиляции. Позже в статье Университета Индиана было продемонстрировано [http://web.archive.org/web/20131101122512/http://ubietylab.net/ubigraph/content/Papers/pdf/CppTuring.pdf кодирование машины Тьюринга в шаблонах C++].
===Java Generics===
Аналогично C++ Templates, Generics, несмотря на свои отличия, тоже оказались полными по Тьюрингу, что было подтверждено Раду Григор в [http://arxiv.org/pdf/1605.05274.pdf статье Кентского Университета].
===mov===
Утилита [https://github.com/xoreaxeaxeax/movfuscator M/o/Vfuscator] превращает любую программу на языке C в огромную последовательность из инструкций mov.
{| cellpadding="3" style="margin-left: auto; margin-right: auto;"
|[[Файл:gcc_asm.png|400px|thumb|Результат работы GCC]]
|[[Файл:mov_asm.png|400px|thumb|Результат работы M/o/Vfuscator]]
|[[Файл:Demo_mov.gif|right|thumb|900px|Простые числа с использованием одной инструкции]]
|}
===HTML5 + CSS3=== ===Minecraft=== ===Little Big Planet=== ===Super Mario World=== ===Braid=== ===Excel=== ==Тьюринговская трясина===
Тьюринговская трясина — жаргонное общее название для языков программирования, которые Тьюринг-полны, но обладают крайне примитивными синтаксисом и семантикой. Они неудобны для практического программирования (из-за трудности написания программ и низкой производительности), зато хорошо подходят для некоторых других задач (доказательство невычислимости некоторых функций, иллюстрация базовых принципов программирования и т. д.). Поэтому они интересны для информатики. Многие эзотерические языки программирования также являются «трясинами Тьюринга».
* [http://wiki.c2.com/?TuringComplete Cunningham & Cunningham, Inc. — Turing Complete]
* [http://cmcmsu.no-ip.info/download/alg.lang.completeness.pdf А. А. Вылиток. Об алгоритмической полноте некоторых языков программирования]
* [httpshttp://ethclassic.ru/2016/10/21/turing-completeness-reality/ «Умные контракты»: полнота по Тьюрингу и реальность] * [http://habrahabr.ru/post/231897/ Хабрахабр — Является ли HTML языком программирования?] * [http://web.archive.org/web/20131101122512/http://ubietylab.net/ubigraph/content/Papers/pdf/CppTuring.pdf Todd L. Veldhuizen — C++ Templates are Turing Complete] * [http://arxiv.org/pdf/1605.05274.pdf Radu Gregore — Java Generics are Turing Complete]
