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

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

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

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

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

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

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

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

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Примеры

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

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

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

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

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

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

Правило 110 и игры Конвея жизни , как клеточные автоматы , являются Тьюринг.

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

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

Программное обеспечение:

Видеоигры:

Социальные медиа:

Карточные игры:

Игры с нулевым лицом (симуляторы):

Вычислительные языки:

Компьютерное железо:

  • инструкция x86 MOV

Биология:

Не полные по Тьюрингу языки

Существует множество вычислительных языков, которые не являются полными по Тьюрингу. Одним из таких примеров является набор регулярных языков , которые генерируются регулярными выражениями и распознаются конечными автоматами . Более мощным, но все же не полным по Тьюрингу расширением конечных автоматов является категория выталкивающих автоматов и контекстно-свободных грамматик , которые обычно используются для генерации деревьев синтаксического анализа на начальной стадии компиляции программы . Дополнительные примеры включают некоторые из ранних версий языков пиксельных шейдеров, встроенных в расширения Direct3D и OpenGL .

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

Хотя (нетипизированное) лямбда-исчисление является полным по Тьюрингу, просто типизированное лямбда-исчисление - нет.

Языки данных

Понятие полноты по Тьюрингу не применяется к таким языкам, как XML , HTML , JSON и YAML , поскольку они обычно используются для представления структурированных данных, а не для описания вычислений. Их иногда называют языками разметки или, более правильно, «языками-контейнерами» или «языками описания данных».

Смотрите также

Примечания

использованная литература

дальнейшее чтение

внешние ссылки