Вычислимость

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

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

Проблемы

Центральной идеей вычислимости является идея ( вычислительной ) проблемы , которая представляет собой задачу, вычислимость которой можно исследовать.

Существует два основных типа проблем:

Проблема принятия решения фиксирует набор S , который может быть набором строк, натуральных чисел или других объектов, взятых из некоторого большего U. набора Конкретный пример проблемы состоит в том, чтобы решить, по данному элементу u из U , находится ли u в S . Например, пусть U — множество натуральных чисел, а S — множество простых чисел. Соответствующая проблема принятия решения соответствует проверке на простоту .
Функциональная задача состоит из функции f из множества U в множество V . Примером проблемы является вычисление по данному элементу u в U соответствующего элемента f ( u ) в V . Например, U и V могут быть набором всех конечных двоичных строк, а f может брать строку и возвращать строку, полученную перестановкой цифр входных данных (таким образом, f(0101) = 1010).

Другие типы проблем включают проблемы поиска и проблемы оптимизации .

Одна из целей теории вычислимости — определить, какие проблемы или классы проблем могут быть решены в каждой модели вычислений.

Формальные модели вычислений

Модель вычислений — это формальное описание определенного типа вычислительного процесса. Описание часто принимает форму абстрактной машины , предназначенной для выполнения поставленной задачи. Общие модели вычислений, эквивалентные машине Тьюринга (см. тезис Чёрча – Тьюринга ), включают:

Лямбда-исчисление: Вычисление состоит из исходного лямбда-выражения (или двух, если вы хотите разделить функцию и ее входные данные) плюс конечной последовательности лямбда-членов, каждый из которых выводится из предыдущего с помощью одного применения бета-редукции .
Комбинаторная логика: Концепция, имеющая много общего с $\lambda$ -исчислении, но существуют и важные различия (например, комбинатор Y с фиксированной точкой имеет нормальную форму в комбинаторной логике, но не в $\lambda$ -исчисление). Комбинаторная логика разрабатывалась с большими амбициями: понять природу парадоксов, сделать основы математики более экономичными (концептуально), исключить понятие переменных (таким образом, прояснив их роль в математике).
μ-рекурсивные функции: Вычисление состоит из µ-рекурсивной функции, т.е. ее определяющей последовательности, любого входного значения(й) и последовательности рекурсивных функций, появляющихся в определяющей последовательности с входными и выходными данными. Таким образом, если в определяющей последовательности рекурсивной функции $f (x)$ фигурируют функции $g (x)$ и $h (x, y)$ , то члены вида $g (5) = 7$ или $h (3,2) = 10$ может появиться. Каждая запись в этой последовательности должна быть применением базовой функции или следовать из записей выше с помощью композиции , примитивной рекурсии или μ-рекурсии . Например, если $f (x) = h (x, g (x))$ , то для $f (5) = 3$ появления $выше должны встречаться такие термины, как g (5) = 6$ и $h (5,6) = 3$ . Вычисление завершается только в том случае, если последний член дает значение рекурсивной функции, примененной к входным данным.
Системы перезаписи строк: Включает алгоритмы Маркова , которые используют грамматические правила для работы со строками символов; также Пост-каноническая система .
Зарегистрировать машину: Теоретическая идеализация компьютера. Есть несколько вариантов. В большинстве из них каждый регистр может хранить натуральное число (неограниченного размера), а инструкции просты (и немногочисленны), например, существуют только декрементация (в сочетании с условным переходом) и инкремент (и остановка). Отсутствие бесконечного (или динамически растущего) внешнего хранилища (видимого в машинах Тьюринга) можно понять, заменив его роль методами нумерации Гёделя : тот факт, что каждый регистр содержит натуральное число, дает возможность представить сложную вещь (например, последовательность или матрица и т. д.) соответствующим огромным натуральным числом — однозначность как представления, так и интерпретации может быть установлена на основе теоретико-числовых основ этих методов.
Машина Тьюринга: Также похож на конечный автомат, за исключением того, что входные данные предоставляются на «ленте» выполнения, с которой машина Тьюринга может читать, записывать или перемещаться вперед и назад мимо своей «головки» чтения/записи. Ленте дают возможность вырасти до произвольного размера. Машина Тьюринга способна выполнять сложные вычисления, длительность которых может быть произвольной. Эта модель, пожалуй, самая важная модель вычислений в информатике, поскольку она имитирует вычисления в отсутствие заранее определенных ограничений ресурсов.
Многоленточная машина Тьюринга: Здесь может быть более одной ленты; более того, на ленте может быть несколько головок. Удивительно, но любые вычисления, которые могут быть выполнены на машине такого типа, также могут быть выполнены на обычной машине Тьюринга, хотя последняя может быть медленнее или требовать большей общей области своей ленты.
П'': Подобно машинам Тьюринга, P′′ использует бесконечную ленту символов (без произвольного доступа) и довольно минималистичный набор инструкций. Но эти инструкции очень разные, поэтому, в отличие от машин Тьюринга, P'' не нужно поддерживать отдельное состояние, поскольку все функции, подобные памяти, могут быть обеспечены только лентой. Вместо перезаписи текущего символа он может выполнить над ним модульное арифметическое приращение. P'' также имеет пару инструкций для цикла проверки пустого символа. Несмотря на свой минималистичный характер, он стал родительским формальным языком реализованного и (для развлечения) используемого языка программирования под названием Brainfuck .

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

Различные модели вычислений способны решать разные задачи. Один из способов измерить мощность вычислительной модели — изучить класс формальных языков , которые может генерировать эта модель; таким образом иерархия языков Хомского получается .

Другие ограниченные модели вычислений включают:

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

Мощность автоматов

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

Мощность конечных автоматов

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

Примером такого языка является набор всех строк, состоящих из букв «a» и «b», которые содержат равное количество букв «a» и «b». Чтобы понять, почему этот язык не может быть правильно распознан конечным автоматом, предположим сначала, что такой автомат M существует. M должно иметь некоторое количество состояний n . Теперь рассмотрим строку x, состоящую из $(n+1)$ за 'a следует $(n+1)$ 'б'.

Поскольку M читает в x , в машине должно быть какое-то состояние, которое повторяется так, как она читает первую серию букв "a", поскольку существуют $(n+1)$ «а и только n состояний» по принципу «ячейки» . Назовем это состояние S и далее пусть d будет количеством букв «a», которые наша машина прочитала, чтобы перейти от первого появления S к некоторому последующему появлению во время последовательности «a». Таким образом, мы знаем, что при втором появлении S мы можем добавить дополнительный d (где $d>0$ ) 'a's и мы снова окажемся в состоянии S . Это означает, что мы знаем, что строка $(n+d+1)$ 'a должны оказаться в том же состоянии, что и строка $(n+1)$ 'как. Это означает, что если наша машина принимает x , она также должна принять строку $(n+d+1)$ за 'a следует $(n+1)$ 'b', чего нет в языке строк, содержащих равное количество 'a' и 'b'. Другими словами, M не может правильно отличить строку с равным количеством символов «a» и «b» от строки с $(n+d+1)$ 'а и $n+1$ 'б'.

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

Мощность понижающих автоматов

Ученые-компьютерщики определяют язык, который может быть принят автоматом с pushdown, как контекстно-свободный язык , который можно определить как контекстно-свободную грамматику . Язык, состоящий из строк с равным количеством букв «a» и «b», который, как мы показали, не является обычным языком, может быть определен с помощью автомата с проталкиванием вниз. Кроме того, в целом автомат с выталкиванием вниз может вести себя точно так же, как конечный автомат, поэтому он может решать любой регулярный язык. Таким образом, эта модель вычислений является строго более мощной, чем конечные автоматы.

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

Мощность машин Тьюринга

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

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

Оказывается, машина Тьюринга — чрезвычайно мощная модель автоматов. Попытки изменить определение машины Тьюринга, чтобы создать более мощную машину, неожиданно потерпели неудачу. Например, добавление дополнительной ленты к машине Тьюринга, дающей ей двумерную (или трех- или любую другую) бесконечную поверхность для работы, может быть смоделировано машиной Тьюринга с помощью базовой одномерной ленты. Таким образом, эти модели не являются более мощными. Фактически, следствием тезиса Чёрча-Тьюринга является то, что не существует разумной модели вычислений, которая могла бы решать языки, которые не могут быть решены машиной Тьюринга.

Тогда возникает вопрос: существуют ли языки, которые рекурсивно перечислимы, но не рекурсивны? И, более того, существуют ли языки, которые даже не являются рекурсивно перечислимыми?

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

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

Учитывая описание машины Тьюринга и ее начального ввода, определите, останавливается ли когда-либо программа при выполнении на этом входе (завершается). Альтернатива состоит в том, что он работает вечно, не останавливаясь.

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

То есть единственный общий способ узнать наверняка, остановится ли данная программа на определенном входе во всех случаях, — это просто запустить ее и посмотреть, остановится ли она. Если оно остановится, то вы знаете, что оно остановится. Однако, если оно не остановится, вы никогда не узнаете, остановится ли оно в конечном итоге. Язык, состоящий из всех описаний машин Тьюринга в сочетании со всеми возможными входными потоками, на которых эти машины Тьюринга в конечном итоге остановятся, не является рекурсивным. Поэтому проблему остановки называют невычислимой или неразрешимой .

Расширение проблемы остановки называется теоремой Райса , которая утверждает, что неразрешимо (вообще), обладает ли данный язык каким-либо конкретным нетривиальным свойством.

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

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

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

Модели на основе параллелизма

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

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

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

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

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

1=\sum _{n=1}^{\infty }{\frac {1}{2^{n}}}={\frac {1}{2}}+{\frac {1}{4}}+{\frac {1}{8}}+{\frac {1}{16}}+\cdots

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

машины Oracle

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

Ограничения гипервычислений

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

См. также

Ссылки

Майкл Сипсер (1997). Введение в теорию вычислений . Издательство ПВС. ISBN 0-534-94728-Х . Часть вторая: Теория вычислимости, главы 3–6, стр. 123–222.
Христос Пападимитриу (1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1 . Глава 3: Вычислимость, стр. 57–70.
С. Барри Купер (2004). Теория вычислимости (1-е изд.). Чепмен и Холл/CRC. ISBN 978-1-58488-237-4 .