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