Что значит тьюринг полный язык

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

Содержание

Введение [ править ]

Определение:

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

Определение:

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

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

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

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

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

Критерии Тьюринг-полноты [ править ]

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

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

• Фиксированное описание (формальность [1] ).

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

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

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

• Наличие циклов [math]<\bf while>[/math] с прерыванием или эквивалентных им конструкций.

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

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

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

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

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

Assembly language [ править ]

Язык Ассемблера достаточно примитивен относительно языков программирования высокого уровня: он рассчитан на архитектуру с конечной памятью и работает с конечным набором регистров. Однако, не был бы он полным по Тьюрингу, не были бы Тьюринг-полны и любые высокоуровневые языки программирования.

Всё необходимое для машины Тьюринга на asm можно сделать примерно так:

И далее использовать инструкцию [math]\mathrm[/math] или ей подобную, чтобы выполнять определённую последовательность команд при определённом текущем значении, таким образом обеспечив ветвление.

Pascal [ править ]

Язык Pascal позволяет смоделировать ленту машины Тьюринга с помощью двунаправленного списка из переменных, создаваемых оператором [math]\mathrm[/math] , семантика которого не предполагает отказа в создании переменной. Также с помощью списков можно смоделировать сколь угодно большие числа. Стандарт не накладывает никаких ограничений: указательный тип абстрактен, множество значений указательного типа языком не ограничено. В Паскале есть еще один тип данных с неограниченным множеством значений, файловый, также пригодный для моделирования ленты машины Тьюринга и представления больших чисел. Достаточно утверждений для очевидности Тьюринг-полноты языка Pascal.

C [ править ]

В языке C нет высокоуровневого понятия переменной (в смысле Паскаля), есть объекты (object), хранящиеся в памяти как последовательно расположенные байты,имеющие адрес (байты в свою очередь состоят из неадресуемых битов). Целые типы ограничены (конечное множество значений), указатель отождествляется с адресом, постулируется возможность хранить адрес в целочисленной переменной (int или long — зависит от реализации), откуда следует ограниченность множества значений указателей, а стало быть, и ограниченность адресного пространства C-машины. То есть язык C, как и язык ассемблера, ориентирован на архитектуру с конечной памятью. Файл не является типом данных языка C, в отличие от Паскаля. Это вещь из окружения, для работы с которой есть операции над потоками в виде набора библиотечных функций. Тип fpos_t, принятый в стандарте C для позиционирования файлов, постулируется как «отличный от массива тип данных (object type)». Следовательно, множество значений этого типа конечно, а значит, максимальная длина файла в языке C ограничена сверху.

SQL [ править ]

Сам по себе SQL никогда не считался полным по Тьюрингу языком. Однако, у него существует множество расширений, позволяющих делать рекурсивные запросы, циклы, списки, деревья и пр., например, с помощью PostgreSQL [2] . Более того, на в 2011 г. Habrahabr появилась статья, где показана машина Тьюринга на SQL [3] (в реализации Firebird 2.1, который ограничивает вложенность рекурсивных запросов до 2014 уровней). Тем не менее, всё ещё остаётся ограниченное query execution time.

HTML [ править ]

HTML можно назвать языком программирования только в контексте формальной полемики. На деле он является языком гипертекстовой разметки и ни чем больше. Т. е. на HTML можно совершить только некоторую ограниченную совокупность действий, интерпретируемых браузером, однако никто не запрещает сделать язык, идентичный по синтаксису с HTML, но интерпретируемый совершенно по другому таким образом, чтобы он был полным по Тьюрингу.

Некоторые другие ЯП [ править ]

Название языка	Год изобретения	Парадигма	Уровень	Зависимость от архитектуры процессора	Полнота по Тьюрингу
C	1972	Процедурный	Низкий	зав. от ISO	Да
C++	1983	Мультипарадигменный	Высокий/Низкий	Нет	Да
Язык Ассемблера	1950	Полнофункциональный	Низкий	Да	Да
SQL	1989	Декларативный	Высокий	Нет	Нет
Haskell	1990	Функциональный	Высокий	Нет	Да
HTML	1986	Декларативный	Высокий	Нет	Нет
CSS	1996	Декларативный	Высокий	Нет	Нет
Java	1995	Объектно-ориентированный	Высокий	Нет	Да
JavaScript	1995	Объектно-ориентированный	Высокий	Нет	Да
Python	1991	Объектно-ориентированный	Высокий	Нет	Да
XML	1998	Декларативный	Высокий	Нет	Нет
Brainfuck	1993	Эзотерический	Низкий	Да	Да
Whitespace	2003	Эзотерический	Низкий	Да	Да

Интересные случаи полноты по Тьюрингу [ править ]

Шаблоны C++ [ править ]

Шаблоны C++ позволяют производить сложные вычисления ещё на стадии компиляции программы. Впервые это было продемонстрировано Эрвином Унрухом, который реализовал рекурсивный алгоритм распознавания простых чисел в процессе компиляции. Позже в статье Университета Индиана было продемонстрировано кодирование машины Тьюринга в шаблонах C++ [4] .

Java Generics [ править ]

Аналогично C++ Templates, Generics, несмотря на свои отличия, тоже оказались полными по Тьюрингу, что было подтверждено Раду Григор в одной из статей Кентского Университета [5] .

URISC [ править ]

URISC (от англ. Ultimate RISC) — предельный случай процессора типа RISC (буквально: компьютер с предельно сокращённым набором инструкций), который умеет выполнять одну-единственную инструкцию. Обычно это «вычесть и пропустить следующую инструкцию, если вычитаемое было больше уменьшаемого» (англ. «reverse-subtract and skip if borrow»). Аналогичная концепция, основанная именно на «вычесть и перейти, если результат не положительный» (англ. «subtract and branch unless positive»), называется SUBLEQ.

URISC также известен в современной литературе как OISC (англ. One Instruction Set Computer) и является полным по Тьюрингу.

mov [ править ]

Утилита M/o/Vfuscator превращает любую программу на языке C в огромную последовательность из инструкций [math]\mathrm [/math] [6] .

Источник

Полнота по Тьюрингу — Turing completeness

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

Родственная концепция — это концепция эквивалентности Тьюринга — два компьютера P и Q называются эквивалентными, если P может моделировать Q, а Q может моделировать P. Тезис Черча – Тьюринга предполагает, что любая функция, значения которой могут быть вычислены с помощью алгоритма, может быть вычислена с помощью Машина Тьюринга, и, следовательно, если какой-либо реальный компьютер может моделировать машину Тьюринга, то это эквивалент машины Тьюринга по Тьюрингу. Универсальная машина Тьюринга может быть использована для имитации любой машины Тьюринга и выдвижением вычислительных аспектов любого возможного реального компьютера.

Чтобы показать, что что-то является полным по Тьюрингу, достаточно показать, что это может быть использовано для моделирования некоторой полной системы по Тьюрингу. Например, императивный язык является полным по Тьюрингу, если у него есть условное ветвление (например, операторы «if» и «goto» или инструкция « переход при нулевом значении»; см. Компьютер с одним набором инструкций ) и возможность изменять произвольные объем памяти (например, возможность поддерживать произвольное количество элементов данных). Конечно, никакая физическая система не может иметь бесконечную память; но если игнорировать ограничение конечной памяти, большинство языков программирования в остальном являются полными по Тьюрингу.

СОДЕРЖАНИЕ

Нематематическое использование

В разговорной речи термины «полный по Тьюрингу» и «эквивалент по Тьюрингу» используются для обозначения того, что любой реальный компьютер общего назначения или компьютерный язык может приблизительно имитировать вычислительные аспекты любого другого реального компьютера общего назначения или компьютерный язык.

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

Формальные определения

В теории вычислимости для описания вычислительной мощности вычислительной системы (например, абстрактной машины или языка программирования ) используются несколько тесно связанных терминов :

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

История

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

Чарльз Бэббидж «s аналитического двигатель (1830) был бы первым Тьюрингу машиной , если он был построен в то время он был разработан. Бэббидж ценил, что машина способна на великие вычисления, включая примитивные логические рассуждения, но он не понимал, что никакая другая машина не может работать лучше. С 1830-х до 1940-х годов были построены и усовершенствованы механические вычислительные машины, такие как сумматоры и умножители, но они не могли выполнять условный переход и, следовательно, не были полными по Тьюрингу.

В конце 19 века Леопольд Кронекер сформулировал понятие вычислимости, определив примитивно рекурсивные функции . Эти функции могут быть вычислены механически, но их недостаточно для создания универсального компьютера, потому что инструкции, которые их вычисляют, не допускают бесконечного цикла. В начале 20 века Дэвид Гильберт возглавил программу аксиоматизации всей математики с помощью точных аксиом и точных логических правил вывода, которые могли быть выполнены машиной. Вскоре стало ясно, что небольшого набора правил дедукции достаточно, чтобы произвести следствия любого набора аксиом. Эти правила были доказаны Куртом Гёделем в 1930 году, чтобы их было достаточно для построения каждой теоремы.

Фактическое понятие вычислений было выделено вскоре после этого, начиная с теоремы Гёделя о неполноте . Эта теорема показала, что системы аксиом были ограничены при рассуждении о вычислениях, которые выводят их теоремы. Черч и Тьюринг независимо продемонстрировали, что Entscheidungsproblem Гильберта (проблема решения) неразрешима, тем самым выявив вычислительное ядро ​​теоремы о неполноте. Эта работа, наряду с работой Гёделя над общерекурсивными функциями , установила, что существуют наборы простых инструкций, которые, будучи собраны вместе, могут производить любые вычисления. Работа Гёделя показала, что понятие вычисления по сути уникально.

В 1941 году Конрад Цузе завершил разработку компьютера Z3 . Цузе в то время не был знаком с работами Тьюринга по вычислимости. В частности, в Z3 не хватало специальных средств для условного перехода, что не позволяло ему быть полным по Тьюрингу. Однако в 1998 году Рохас показал, что Z3 может выполнять условные переходы и, следовательно, завершаться по Тьюрингу, используя некоторые из его функций непреднамеренным образом.

Теория вычислимости

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

Классическим примером является проблема остановки : создать алгоритм, который принимает в качестве входных данных программу на некотором полном по Тьюрингу языке и некоторые данные, которые должны быть переданы в эту программу, и определяет, остановится ли программа, работающая с входными данными, в конечном итоге или продолжит навсегда. Создать алгоритм, который может это сделать для некоторых входных данных, тривиально , но в целом сделать это невозможно. Для любой характеристики конечного результата программы невозможно определить, сохранится ли эта характеристика.

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

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

Оракулы Тьюринга

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

Цифровая физика

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

Примеры

Вычислительные системы (алгебры, исчисления), которые рассматриваются как полные по Тьюрингу, предназначены для изучения теоретической информатики . Они должны быть как можно более простыми, чтобы было легче понять пределы вычислений. Вот несколько:

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

• Все универсальные языки широко используются.
  • Языки процедурного программирования, такие как C , Pascal .
  • Объектно-ориентированные языки, такие как Java , Smalltalk или C # .
  • Multi-парадигме языков , таких как Ada , C ++ , Common Lisp , Fortran , Object Pascal , Perl , Python , R .
• Большинство языков, использующих менее распространенные парадигмы:
  • Функциональные языки, такие как Lisp и Haskell .
  • Языки логического программирования, такие как Пролог .
  • Макропроцессоробщего назначения, например m4 .
  • Декларативные языки, такие как XSLT .
  • VHDL и другие языки описания оборудования.
  • TeX , система набора.
  • Эзотерические языки программирования , форма математического отдыха, в которой программисты решают, как создавать базовые программные конструкции на чрезвычайно сложном, но математически эквивалентном Тьюрингу языке.

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

Полнота по Тьюрингу — это абстрактное утверждение способности, а не рецепт конкретных языковых функций, используемых для реализации этой способности. Функции, используемые для достижения полноты по Тьюрингу, могут быть совершенно разными; Системы Fortran будут использовать конструкции цикла или, возможно, даже операторы goto для достижения повторения; В Haskell и Prolog, в которых почти не было цикла, использовалась бы рекурсия . Большинство языков программирования описывают вычисления на архитектурах фон Неймана , которые имеют память (RAM и регистр) и блок управления. Эти два элемента делают эту архитектуру полной по Тьюрингу. Даже чистые функциональные языки являются полными по Тьюрингу.

Полнота по Тьюрингу в декларативном SQL реализуется с помощью рекурсивных общих табличных выражений . Неудивительно, что процедурные расширения SQL ( PLSQL и т. Д.) Также являются полными по Тьюрингу. Это иллюстрирует одну причину, по которой относительно мощные неполные по Тьюрингу языки встречаются редко: чем мощнее язык изначально, тем сложнее задачи, к которым он применяется, и тем скорее его недостаточная полнота воспринимается как недостаток, поощряя его использование. расширение, пока оно не станет полным по Тьюрингу.

Нетипизированное лямбда-исчисление является полным по Тьюрингу, но многие типизированные лямбда-исчисления, включая Систему F , нет. Ценность типизированных систем основана на их способности отображать большинство типичных компьютерных программ при одновременном обнаружении большего количества ошибок.

Непреднамеренная полнота по Тьюрингу

Некоторые игры и другое программное обеспечение являются полными по Тьюрингу случайно, то есть не намеренно.

Источник