Вычислимость — это способность решать проблему эффективным способом. Это ключевая тема области теории вычислимости в математической логике и теории вычислений в информатике . Вычислимость проблемы тесно связана с существованием алгоритма для ее решения.
Наиболее широко изучаемыми моделями вычислимости являются вычислимые по Тьюрингу и μ-рекурсивные функции , а также лямбда-исчисление , все из которых имеют эквивалентную вычислительную мощность. Другие формы вычислимости также изучаются: понятия вычислимости, слабее машин Тьюринга, изучаются в теории автоматов , в то время как понятия вычислимости, сильнее машин Тьюринга, изучаются в области гипервычислений .
Центральной идеей вычислимости является идея ( вычислительной ) проблемы , то есть задачи, вычислимость которой можно исследовать.
Существует два основных типа проблем:
Другие типы проблем включают проблемы поиска и проблемы оптимизации .
Одной из целей теории вычислимости является определение того, какие задачи или классы задач могут быть решены в каждой модели вычислений.
Модель вычислений — это формальное описание определенного типа вычислительного процесса. Описание часто принимает форму абстрактной машины , которая предназначена для выполнения поставленной задачи. Общие модели вычислений, эквивалентные машине Тьюринга (см. тезис Чёрча–Тьюринга ), включают:
В дополнение к общим вычислительным моделям, некоторые более простые вычислительные модели полезны для специальных, ограниченных приложений. Регулярные выражения , например, определяют шаблоны строк во многих контекстах, от офисного программного обеспечения до языков программирования . Другой формализм, математически эквивалентный регулярным выражениям, конечные автоматы используются в проектировании схем и в некоторых видах решения проблем. Контекстно-свободные грамматики определяют синтаксис языка программирования. Недетерминированные магазинные автоматы являются другим формализмом, эквивалентным контекстно-свободным грамматикам.
Различные модели вычислений способны выполнять различные задачи. Один из способов измерения мощности вычислительной модели — изучить класс формальных языков , которые может генерировать эта модель; таким образом получается иерархия языков Хомского .
Другие ограниченные модели вычислений включают в себя:
Имея эти вычислительные модели на руках, мы можем определить, каковы их пределы. То есть, какие классы языков они могут принять?
Специалисты по информатике называют любой язык, который может быть принят конечным автоматом, регулярным языком . Из-за ограничения, что число возможных состояний в конечном автомате конечно, мы можем видеть, что для того, чтобы найти язык, который не является регулярным, мы должны построить язык, который потребовал бы бесконечного числа состояний.
Примером такого языка является множество всех строк, состоящих из букв 'a' и 'b', которые содержат равное количество букв 'a' и 'b'. Чтобы понять, почему этот язык не может быть правильно распознан конечным автоматом, предположим сначала, что такой автомат M существует. M должен иметь некоторое количество состояний n . Теперь рассмотрим строку x, состоящую из 'a', за которыми следуют 'b'.
Поскольку M считывает x , в машине должно быть некоторое состояние, которое повторяется при считывании первой серии 'a's, поскольку есть 'a's и только n состояний по принципу ящика . Назовем это состояние S , и далее пусть d будет числом 'a's, которые наша машина считывает, чтобы перейти от первого появления S к некоторому последующему появлению в последовательности 'a'. Тогда мы знаем, что при этом втором появлении S мы можем добавить дополнительное d (где ) 'a's, и мы снова окажемся в состоянии S . Это означает, что мы знаем, что строка 'a's должна оказаться в том же состоянии, что и строка 'a's. Это подразумевает, что если наша машина принимает x , она должна также принимать строку 'a's, за которой следуют 'b's, что не соответствует языку строк, содержащих равное количество 'a's и 'b's. Другими словами, M не может правильно различить строку с равным количеством букв «a» и «b» и строку с буквами «a» и «b».
Мы знаем, следовательно, что этот язык не может быть правильно принят никаким конечным автоматом, и, таким образом, не является регулярным языком. Более общая форма этого результата называется леммой Pumping для регулярных языков , которую можно использовать для того, чтобы показать, что широкие классы языков не могут быть распознаны конечным автоматом.
Специалисты по информатике определяют язык, который может быть принят магазинным автоматом , как Контекстно-свободный язык , который может быть определен как Контекстно-свободная грамматика . Язык, состоящий из строк с равным количеством 'a' и 'b', который, как мы показали, не является регулярным языком, может быть определен магазинным автоматом. Кроме того, в общем случае магазинный автомат может вести себя так же, как конечный автомат, поэтому он может определить любой язык, который является регулярным. Таким образом, эта модель вычислений строго более мощна, чем конечные автоматы.
Однако оказывается, что существуют языки, которые также не могут быть определены с помощью push-down-автомата. Результат аналогичен результату для регулярных выражений и не будет здесь подробно описываться. Существует лемма Pumping для контекстно-свободных языков . Примером такого языка является множество простых чисел.
Машины Тьюринга могут решать любой контекстно-свободный язык, в дополнение к языкам, неразрешимым автоматом с обратным отсчетом, таким как язык, состоящий из простых чисел. Поэтому это строго более мощная модель вычислений.
Поскольку машины Тьюринга обладают способностью «делать резервную копию» на своей входной ленте, машина Тьюринга может работать долгое время способом, который невозможен с другими ранее описанными моделями вычислений. Можно построить машину Тьюринга, которая никогда не закончит работу (остановится) на некоторых входах. Мы говорим, что машина Тьюринга может выбрать язык, если она в конечном итоге остановится на всех входах и даст ответ. Язык, который может быть выбран таким образом, называется рекурсивным языком . Мы можем далее описать машины Тьюринга, которые в конечном итоге остановятся и дадут ответ для любого входа на языке, но которые могут работать вечно для входных строк, которых нет в языке. Такие машины Тьюринга могли бы сказать нам, что данная строка находится в языке, но мы никогда не можем быть уверены на основе ее поведения, что данная строка не находится в языке, поскольку в таком случае он может работать вечно. Язык, который принимается такой машиной Тьюринга, называется рекурсивно перечислимым языком .
Машина Тьюринга, как оказалось, является чрезвычайно мощной моделью автоматов. Попытки изменить определение машины Тьюринга, чтобы создать более мощную машину, на удивление, потерпели неудачу. Например, добавление дополнительной ленты к машине Тьюринга, придание ей двумерной (или трехмерной, или любой другой) бесконечной поверхности для работы, все это может быть смоделировано машиной Тьюринга с базовой одномерной лентой. Таким образом, эти модели не являются более мощными. Фактически, следствием тезиса Чёрча-Тьюринга является то, что не существует разумной модели вычислений, которая могла бы решать языки, которые не могут решаться машиной Тьюринга.
Тогда возникает вопрос: существуют ли языки, которые рекурсивно перечислимы, но не являются рекурсивными? И, более того, существуют ли языки, которые даже не являются рекурсивно перечислимыми?
Проблема остановки — одна из самых известных проблем в информатике, поскольку она имеет глубокие последствия для теории вычислимости и для того, как мы используем компьютеры в повседневной практике. Проблему можно сформулировать так:
Здесь мы задаем не простой вопрос о простом числе или палиндроме, а вместо этого меняем столы и просим машину Тьюринга ответить на вопрос о другой машине Тьюринга. Можно показать (см. основную статью: Проблема остановки ), что невозможно построить машину Тьюринга, которая может ответить на этот вопрос во всех случаях.
То есть, единственный общий способ узнать наверняка, остановится ли данная программа на определенном входе во всех случаях, — просто запустить ее и посмотреть, остановится ли она. Если она остановится, то вы знаете, что она остановится. Однако, если она не остановится, вы никогда не узнаете, остановится ли она в конечном итоге. Язык, состоящий из всех описаний машин Тьюринга, сопряженных со всеми возможными входными потоками, на которых эти машины Тьюринга в конечном итоге остановятся, не является рекурсивным. Поэтому проблема остановки называется невычислимой или неразрешимой .
Расширение проблемы остановки называется теоремой Райса , которая утверждает, что в общем случае невозможно определить, обладает ли данный язык каким-либо конкретным нетривиальным свойством.
Однако проблему остановки легко решить, если мы допустим, что машина Тьюринга, которая ее решает, может работать вечно, если ей подан вход, который является представлением машины Тьюринга, которая сама не останавливается. Таким образом, останавливающийся язык рекурсивно перечислим. Однако возможно построить языки, которые даже не являются рекурсивно перечислимыми.
Простым примером такого языка является дополнение к останавливающемуся языку; то есть язык, состоящий из всех машин Тьюринга, сопряженных со строками ввода, где машины Тьюринга не останавливаются на своем вводе. Чтобы увидеть, что этот язык не является рекурсивно перечислимым, представьте, что мы строим машину Тьюринга M , которая способна дать определенный ответ для всех таких машин Тьюринга, но что она может работать вечно на любой машине Тьюринга, которая в конечном итоге остановится. Затем мы можем построить другую машину Тьюринга , которая моделирует работу этой машины, а также моделирует непосредственно выполнение машины, заданной на входе, чередуя выполнение двух программ. Поскольку прямая симуляция в конечном итоге остановится, если моделируемая ею программа остановится, и поскольку по предположению симуляция M в конечном итоге остановится, если входная программа никогда не остановится, мы знаем, что в конечном итоге остановит одну из своих параллельных версий. Таким образом, является решателем для проблемы остановки. Однако ранее мы показали, что проблема остановки неразрешима. У нас есть противоречие, и мы таким образом показали, что наше предположение о существовании M неверно. Дополнение останавливающегося языка, таким образом, не является рекурсивно перечислимым.
Разработан ряд вычислительных моделей, основанных на параллелизме , включая параллельную машину с произвольным доступом и сеть Петри . Эти модели параллельных вычислений до сих пор не реализуют никаких математических функций, которые не могут быть реализованы машинами Тьюринга.
Тезис Чёрча –Тьюринга предполагает, что не существует эффективной модели вычислений, которая может вычислять больше математических функций, чем машина Тьюринга. Специалисты по информатике придумали множество разновидностей гиперкомпьютеров , моделей вычислений, которые выходят за рамки вычислимости Тьюринга.
Представьте себе машину, в которой каждый шаг вычисления требует половины времени предыдущего шага (и, как мы надеемся, половины энергии предыдущего шага...). Если мы нормализуем к 1/2 единицы времени количество времени, требуемое для первого шага (и к 1/2 единицы энергии количество энергии, требуемое для первого шага...), выполнение потребует
единицу времени (и 1 единицу энергии...) для выполнения. Этот бесконечный ряд сходится к 1, что означает, что эта машина Зенона может выполнить счетно бесконечное количество шагов за 1 единицу времени (используя 1 единицу энергии...). Эта машина способна решить проблему остановки, напрямую симулируя выполнение машины. По сути, любой сходящийся бесконечный [должен быть доказуемо бесконечным] ряд будет работать. Предполагая, что бесконечный ряд сходится к значению n , машина Зенона завершит счетно бесконечное выполнение за n единиц времени.
Так называемые машины Oracle имеют доступ к различным "оракулам", которые предоставляют решение для определенных неразрешимых проблем. Например, машина Тьюринга может иметь "останавливающий оракул", который немедленно отвечает, остановится ли данная машина Тьюринга когда-либо на данном входе. Эти машины являются центральной темой изучения в теории рекурсии .
Даже эти машины, которые, казалось бы, представляют собой предел автоматов, которые мы могли бы себе представить, сталкиваются со своими собственными ограничениями. Хотя каждая из них может решить проблему остановки для машины Тьюринга, они не могут решить свою собственную версию проблемы остановки. Например, машина Oracle не может ответить на вопрос, остановится ли когда-либо данная машина Oracle.
