Тьюринг-полнота и теория относительной вычислимости

Введение

Способность вычислительной системы имитировать машины Тьюринга, использование этого термина в теории относительной вычислимости машинами-оракулами.

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

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

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

История

Полнота Тьюринга важна тем, что любой реальный проект вычислительного устройства может быть смоделирован универсальной машиной Тьюринга. Тезис Черча-Тьюринга утверждает, что это закон математики, согласно которому универсальная машина Тьюринга, в принципе, может выполнять любые вычисления, которые может выполнить любой другой программируемый компьютер. Это не говорит о затратах на написание программы, времени, необходимом машине для выполнения вычисления, или каких-либо способностях машины, не связанных с вычислениями. Аналитическая машина Чарльза Бэббиджа (1830-е годы) была бы первой машиной, обладающей полнотой Тьюринга, если бы она была построена в то время, когда она была спроектирована. Бэббидж понимал, что машина способна на великие вычислительные свершения, включая примитивные логические рассуждения, но он не осознавал, что никакая другая машина не может сделать лучше. С 1830-х по 1940-е годы строились и совершенствовались механические вычислительные машины, такие как сумматоры и умножители, но они не могли выполнять условные переходы и, следовательно, не были полными по Тьюрингу. В конце XIX века Леопольд Кронекер сформулировал понятия вычислимости, определив примитивные рекурсивные функции. Эти функции могут быть вычислены механически, но их недостаточно для создания универсального компьютера, поскольку инструкции, которые их вычисляют, не допускают бесконечного цикла. В начале XX века Давид Гильберт возглавил программу аксиоматизации всей математики точными аксиомами и точными логическими правилами вывода, которые могла бы выполнять машина. Вскоре стало ясно, что небольшого набора правил вывода достаточно для получения следствий из любого набора аксиом. Эти правила были доказаны Куртом Гёделем в 1930 году как достаточные для получения любой теоремы. Само понятие вычисления было выделено вскоре после этого, начиная с теоремы о неполноте Гёделя. Эта теорема показала, что аксиоматические системы ограничены при рассуждениях о вычислениях, выводящих их теоремы. Черч и Тьюринг независимо друг от друга показали, что проблема Entscheidungsproblem Гильберта (проблема разрешимости) неразрешима, тем самым определив вычислительное ядро теоремы о неполноте. Эта работа, вместе с работой Гёделя над общими рекурсивными функциями, установила, что существуют наборы простых инструкций, которые, будучи объединены, способны выполнять любые вычисления. Работа Гёделя показала, что понятие вычисления по существу уникально. В 1941 году Конрад Цузе завершил создание компьютера Z3. В то время Цузе не был знаком с работой Тьюринга по вычислимости. В частности, Z3 не имел специальных средств для выполнения условного перехода, что исключало его полноту по Тьюрингу. Однако в 1998 году Рохас показал, что Z3 способен моделировать условные переходы и, следовательно, теоретически полон по Тьюрингу. Для этого программа на ленте должна быть достаточно длинной, чтобы выполнить все возможные пути через обе стороны каждой ветви. Первым компьютером, способным к условному ветвлению на практике и, следовательно, полным по Тьюрингу на практике, был ENIAC в 1946 году. Компьютер Z4 Цузе был введен в эксплуатацию в 1945 году, но он не поддерживал условные переходы до 1950 года.

Turing completeness is significant in that every real world design for a computing device can be simulated by a universal Turing machine. The Church–Turing thesis states that this is a law of mathematics that a universal Turing machine can, in principle, perform any calculation that any other programmable computer can. This says nothing about the effort needed to write the program, or the time it may take for the machine to perform the calculation, or any abilities the machine may possess that have nothing to do with computation. Charles Babbage's analytical engine (1830s) would have been the first Turing complete machine if it had been built at the time it was designed. Babbage appreciated that the machine was capable of great feats of calculation, including primitive logical reasoning, but he did not appreciate that no other machine could do better. From the 1830s until the 1940s, mechanical calculating machines such as adders and multipliers were built and improved, but they could not perform a conditional branch and therefore were not Turing complete. In the late 19th century, Leopold Kronecker formulated notions of computability, defining primitive recursive functions. These functions can be calculated by rote computation, but they are not enough to make a universal computer, because the instructions that compute them do not allow for an infinite loop. In the early 20th century, David Hilbert led a program to axiomatize all of mathematics with precise axioms and precise logical rules of deduction that could be performed by a machine. Soon it became clear that a small set of deduction rules are enough to produce the consequences of any set of axioms. These rules were proved by Kurt Gödel in 1930 to be enough to produce every theorem. The actual notion of computation was isolated soon after, starting with Gödel's incompleteness theorem. This theorem showed that axiom systems were limited when reasoning about the computation that deduces their theorems. Church and Turing independently demonstrated that Hilbert's Entscheidungsproblem (decision problem) was unsolvable, thus identifying the computational core of the incompleteness theorem. This work, along with Gödel's work on general recursive functions, established that there are sets of simple instructions, which, when put together, are able to produce any computation. The work of Gödel showed that the notion of computation is essentially unique. In 1941 Konrad Zuse completed the Z3 computer. Zuse was not familiar with Turing's work on computability at the time. In particular, the Z3 lacked dedicated facilities for a conditional jump, thereby precluding it from being Turing complete. However, in 1998, it was shown by Rojas that the Z3 is capable of simulating conditional jumps, and therefore Turing complete in theory. To do this, its tape program would have to be long enough to execute every possible path through both sides of every branch. The first computer capable of conditional branching in practice, and therefore Turing complete in practice, was the ENIAC in 1946. Zuse's Z4 computer was operational in 1945, but it did not support conditional branching until 1950.

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

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

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

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

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

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

Не-турингосовершенные языки

Существует множество вычислительных языков, которые не являются полными по Тьюрингу. Одним из таких примеров является множество регулярных языков, которые генерируются регулярными выражениями и распознаются конечными автоматами. Более мощным, но всё ещё не полным по Тьюрингу расширением конечных автоматов является класс автоматов с магазинной памятью и контекстно-свободных грамматик, которые обычно используются для генерации синтаксических деревьев на начальном этапе компиляции программы. Другие примеры включают некоторые ранние версии языков пиксельных шейдеров, встроенных в расширения Direct3D и OpenGL. В языках функционального программирования, таких как Charity и Epigram, все функции являются тотальными и должны завершаться. Charity использует систему типов и управляющие конструкции, основанные на теории категорий, в то время как Epigram использует зависимые типы. Язык LOOP разработан таким образом, чтобы вычислять только примитивно рекурсивные функции. Все эти языки вычисляют собственные подмножества множества всех вычислимых функций, поскольку полное множество всех вычислимых функций не является вычислимо перечислимым. Кроме того, поскольку все функции в этих языках тотальны, алгоритмы для рекурсивно перечислимых множеств не могут быть записаны на этих языках, в отличие от машин Тьюринга. Хотя (нетипизированное) лямбда-исчисление является полным по Тьюрингу, просто типизированное лямбда-исчисление – нет.