Введение

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

Сила автоматов

Имея в распоряжении эти вычислительные модели, мы можем определить их ограничения. А именно, какие классы языков они способны обрабатывать?

Мощность машин с конечным состоянием

Компьютерные ученые называют любым языком, который может быть принят конечным автоматом, регулярным языком. Из-за ограничения, что число возможных состояний в конечном автомате конечно, следует, что для нахождения языка, который не является регулярным, необходимо построить язык, требующий бесконечного числа состояний. Примером такого языка является множество всех строк, состоящих из букв 'a' и 'b', содержащих одинаковое количество 'a' и 'b'. Чтобы понять, почему этот язык не может быть правильно распознан конечным автоматом, предположим сначала, что такой автомат M существует. M должен иметь некоторое число состояний n. Теперь рассмотрим строку x, состоящую из 'a', за которыми следуют 'b'. По мере того, как M считывает x, должно существовать состояние в автомате, которое повторяется при чтении первой последовательности 'a', поскольку имеется 'a' и только n состояний, согласно принципу Дирихле. Назовем это состояние S, и пусть d – число 'a', которое автомат прочитал, чтобы перейти от первого появления S к последующему появлению в последовательности 'a'. Тогда мы знаем, что при втором появлении S мы можем добавить еще d ('a') и снова окажемся в состоянии S. Это означает, что строка из 'a' завершится в том же состоянии, что и строка из 'a'. Следовательно, если наш автомат принимает x, он также должен принимать строку из 'a', за которыми следуют 'b', которая не принадлежит языку строк, содержащих равное количество 'a' и 'b'. Иными словами, M не может правильно различать строку с равным количеством 'a' и 'b' и строку с 'a' и 'b'. Таким образом, мы знаем, что этот язык не может быть правильно принят каким-либо конечным автоматом и, следовательно, не является регулярным языком. Более общая форма этого результата называется леммой о выкачивании для регулярных языков, которая может быть использована для доказательства того, что широкие классы языков не могут быть распознаны конечными автоматами.

Мощность автоматических устройств

Компьютерные ученые определяют язык, который может быть распознан автоматом с магазинной памятью, как контекстно-свободный язык, который может быть задан контекстно-свободной грамматикой. Язык, состоящий из строк с равным количеством символов 'a' и 'b', который, как мы показали, не является регулярным, может быть распознан автоматом с магазинной памятью. Кроме того, в общем случае, автомат с магазинной памятью может работать как конечный автомат, поэтому он может распознать любой регулярный язык. Таким образом, эта модель вычислений строго мощнее, чем конечные автоматы. Однако, оказывается, существуют языки, которые не могут быть распознаны автоматом с магазинной памятью. Результат аналогичен результату для регулярных выражений и здесь подробно не рассматривается. Для контекстно-свободных языков существует лемма о выкачивании. Примером такого языка является множество простых чисел.

Проблема остановки

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

Дано описание машины Тьюринга и её начальный ввод, определить, завершится ли программа при выполнении на этом вводе (остановится). Альтернатива заключается в том, что она будет выполняться бесконечно, не останавливаясь. Здесь мы задаём не простой вопрос о простом числе или палиндроме, а, напротив, меняем роли и просим машину Тьюринга ответить на вопрос о другой машине Тьюринга. Можно показать (см. основную статью: Проблема останова), что невозможно построить машину Тьюринга, которая могла бы ответить на этот вопрос во всех случаях. То есть, единственный универсальный способ наверняка узнать, завершится ли данная программа на конкретном вводе во всех случаях, — это просто запустить её и посмотреть, остановится ли она. Если она останавливается, то вы знаете, что она остановится. Однако, если она не останавливается, вы можете никогда не узнать, остановится ли она в конечном итоге. Язык, состоящий из всех описаний машин Тьюринга, сопоставленных со всеми возможными входными потоками, на которых эти машины Тьюринга в конечном итоге остановятся, не является рекурсивным. Поэтому проблема останова называется невычислимой или неразрешимой. Обобщением проблемы останова является теорема Райса, которая утверждает, что в общем случае неразрешимо, обладает ли данный язык каким-либо конкретным нетривиальным свойством.

За пределами рекурсивно перечисляемых языков

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

Модели на основе конкуренции

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

Более сильные модели вычислений

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

Бесконечная исполнение

Представьте себе машину, где каждый шаг вычисления требует вдвое меньше времени, чем предыдущий (и, в идеале, вдвое меньше энергии). Если нормализовать время, необходимое для первого шага, до 1/2 единицы времени (а энергию, необходимую для первого шага, до 1/2 единицы энергии), то выполнение потребует единицы времени (и 1 единицы энергии). Этот бесконечный ряд сходится к 1, что означает, что машина Зенона может выполнить счетно бесконечное число шагов за 1 единицу времени (используя 1 единицу энергии). Эта машина способна решить проблему останова, непосредственно моделируя выполнение рассматриваемой машины. В более общем случае, любой сходящийся бесконечный [должен быть доказуемо бесконечным] ряд подойдет. Если предположить, что бесконечный ряд сходится к значению n, машина Зенона завершит счетно бесконечное выполнение за n единиц времени.

Машины Oracle

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

Границы гипервычислений

Даже эти машины, которые, казалось бы, представляют собой предел автоматов, которые мы можем вообразить, сталкиваются с собственными ограничениями. Хотя каждая из них способна решить проблему останова для машины Тьюринга, они не могут решить проблему останова для самих себя. Например, машина Оракул не может ответить на вопрос, остановится ли другая машина Оракул когда-нибудь.