Тьюринг-полнота — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.  
 
Говорят, что задача является Тьюринг-полной, если её можно решить, используя только машину Тьюринга или любую систему, являющуюся Тьюринг-эквивалентной.  
  
 +
Вычислительное устройство является Тьюринг-эквивалентным, если оно может эмулировать машину Тьюринга.
  
 +
В теории вычислимости исполнитель (множество вычисляющих элементов) называется Тьюринг-полным, если на нём можно реализовать любую вычислимую функцию. Другими словами, для каждой вычислимой функции существует вычисляющий её элемент (например, машина Тьюринга) или программа для исполнителя, а все функции, вычисляемые множеством вычислителей, являются вычислимыми функциями (возможно, при некотором кодировании входных и выходных данных).
  
 
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
 
Зачастую Тьюринг-эквивалентные языки программирования называют Тьюринг-полными.
Строка 10: Строка 12:
  
  
−
===Критерии Тьюринг-полноты===
+
==Критерии Тьюринг-полноты==
  
 
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
 
Если на языке программирования можно реализовать машину Тьюринга, то такой язык Тьюринг-полон, и наоборот. Возможность реализации машины Тьюринга на конкретном языке программирования можно грубо описать как перечень требований, которым этот язык должен для этого удовлетворять:
Строка 24: Строка 26:
 
* Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
 
* Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
  
−
* Циклы while с прерыванием или им эквивалентные
+
* Циклы while с прерыванием или эквивалентные им
  
−
* Возможность останавливать выполнение или каким-то образом подавать сигнал о результатах выполнения
+
* Возможность останавливать выполнение (halt) или каким-то образом подавать сигнал о результатах выполнения
  
 
* Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.  
 
* Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.  
  
−
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более 5 бит данных и возвращает не более 5 бит, этот язык не может быть Тьюринг-полным.  
+
* Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.  
  
−
===Тьюринг-полнота и неполнота некоторых языков программирования===
+
==Тьюринг-полнота и неполнота некоторых языков программирования==
  
 
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
 
Доказать Тьюринг-полноту языка программирования можно, предложив способ реализации машины Тьюринга на этом языке. Кроме того, можно предложить интерпретатор языка на другом Тьюринг-полном языке.
 +
 +
===Assembly language===
 +
 +
===Pascal===
 +
 +
===C===
 +
 +
===SQL===
 +
 +
===HTML===
 +
 +
Мы можем назвать HTML языком программирования только в контексте формальной полемики. На деле он является языком гипертекстовой разметки и ни чем больше. Но читатель должен понимать, что если нет четко прописанных стандартов, то никто не запрещает сделать язык, идентичный по синтаксису с HTML, но интерпретируемый совершенно по другому таким образом, чтобы он был полным по Тьюрингу.
 +
 +
===Некоторые другие ЯП===
  
 
{| style="background-color:#CCC;margin:0.5px"
 
{| style="background-color:#CCC;margin:0.5px"
Строка 57: Строка 73:
 
|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"| Язык Ассемблера
 +
|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://wiki.c2.com/?TuringComplete Cunningham & Cunningham, Inc. — Turing Complete]
Строка 80: Строка 170:
 
* [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/ «Умные контракты»: полнота по Тьюрингу и реальность]
+
* [http://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]

Версия 01:02, 8 января 2017

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

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

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

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

Любой полный по Тьюрингу язык достаточно универсальный, чтобы имитировать все другие (хотя и с потенциальным замедлением в работе). Такие языки эквивалентны в рамках вычислений, которые могут произвести. Полные по Тьюрингу языки настолько распространены, что их можно обнаружить даже в примитивных на первый взгляд системах, например, клеточных автоматах или мозаичных системах.

На практике полнота по Тьюрингу — идеализация. Компьютеры имеют ограниченное количество памяти и будут работать ограниченное количество времени, прежде чем их выключат.


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

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

  • Конечность (нет бесконечных символьных множеств и пр.)
  • Фиксированное описание
  • Всегда достаточный объём доступной памяти — в идеале здесь имеется в виду бесконечная память, однако физические рамки не позволяют сделать память ЭВМ бесконечной, поэтому она просто должна быть "always big enough".
  • Неограниченность времени выполнения
  • Возможность функциональной композиции (вызов одной функции из другой, рекурсия)
  • Циклы while с прерыванием или эквивалентные им
  • Возможность останавливать выполнение (halt) или каким-то образом подавать сигнал о результатах выполнения
  • Представление множества натуральных чисел, понятие "следующее число". Возможны другие подобные системы.
  • Поддержка входных и выходных данных (I/O), причём без ограничений в объёме. Если любая программа, написанная на каком-то языке программирования, принимает на вход не более фиксированного n бит данных и возвращает не более n бит, этот язык не может быть Тьюринг-полным.

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

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

Assembly language

Pascal

C

SQL

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.

Результат работы GCC
Результат работы M/o/Vfuscator
Простые числа с использованием одной инструкции

HTML5 + CSS3

Minecraft

Little Big Planet

Super Mario World

Braid

Excel

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

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

Тезис Чёрча-Тьюринга

См. также

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

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Тьюринг-полнота&oldid=59216»