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

редактировать

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

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

Содержание

1 Проблемы
2 Формальные модели вычислений
3 Мощность автоматов
- 3.1 Мощность конечных автоматов
- 3.2 Мощность выталкивающих автоматов
- 3.3 Мощность машин Тьюринга
  - 3.3.1 Проблема остановки.
- 6 См. Также
- 7 Ссылки
Проблемы
Центральная идея вычислимости - это (вычислительная ) проблема, которая является задачей чья вычислимость может быть исследована.

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

Одна из целей теории вычислимости - определить, какие проблемы или классы проблем могут быть решены в каждой модели вычисления.
Формальные модели вычислений
A Модель вычислений - это формальное описание определенного типа вычислительного процесса. Описание часто принимает форму абстрактной машины, которая предназначена для выполнения поставленной задачи. Общие модели вычислений, эквивалентные машине Тьюринга (см. тезис Черча – Тьюринга ), включают:
Лямбда-исчисление
Вычисление состоит из начального лямбда-выражения (или двух, если вы хотите разделить функцию и ее вход) плюс конечная последовательность лямбда-членов, каждый из которых выводится из предыдущего члена одним применением бета-редукции.
Комбинаторная логика
Концепция, которая имеет много общего с $λ {\ displaystyle \ lambda}$ $\ lambda$ -calculus, но также существуют важные различия (например, комбинатор с фиксированной точкой Y имеет нормальную форму в комбинаторной логике, но не в $λ {\ displaystyle \ lambda}$ $\ 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 ′ ′ не нуждается в поддержании отдельного состояния, потому что все «подобные памяти» функциональные возможности могут быть обеспечены только с помощью ленты. Вместо перезаписи текущего символа он может выполнять модульное арифметическое приращение к нему. P ′ ′ также имеет пару инструкций для цикла, проверяющего пустой символ. Несмотря на свой минималистичный характер, он стал родительским формальным языком реализованного и (для развлечения) используемого языка программирования, называемого Brainfuck.
В дополнение к общим вычислительным моделям, некоторые более простые вычислительные модели полезны для специальных, ограниченных приложений.. Регулярные выражения, например, определяют шаблоны строк во многих контекстах, от офисного программного обеспечения до языков программирования. Другой формализм, математически эквивалентный регулярным выражениям, Конечные автоматы используются в схемотехнике и в некоторых видах решения проблем. Контекстно-свободные грамматики определяют синтаксис языка программирования. Недетерминированные выталкивающие автоматы - еще один формализм, эквивалентный контекстно-свободным грамматикам.

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

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

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

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

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

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

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

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

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

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

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

Простым примером такого языка является дополнение к останавливающемуся языку; это язык, состоящий из всех машин Тьюринга в паре с входными строками, где машины Тьюринга не останавливаются на вводе. Чтобы увидеть, что этот язык не является рекурсивно перечислимым, представьте, что мы конструируем машину Тьюринга M, которая способна дать определенный ответ для всех таких машин Тьюринга, но что она может работать вечно на любой машине Тьюринга, которая в конце концов остановится. Затем мы можем построить другую машину Тьюринга $M ′ {\ displaystyle M '}$ $M'$ , которая имитирует работу этой машины, наряду с непосредственным моделированием выполнения машины, указанной во входных данных, путем чередования выполнение двух программ. Поскольку прямое моделирование в конечном итоге остановится, если программа, которую оно имитирует, остановится, и поскольку по предположению, моделирование M в конечном итоге остановится, если программа ввода никогда не остановится, мы знаем, что $M ′ {\ displaystyle M '}$ $M'$ в конечном итоге остановит одну из своих параллельных версий. $M ′ {\ displaystyle M '}$ $M'$ , таким образом, решает проблему остановки. Однако ранее мы показали, что проблема остановки неразрешима. Получили противоречие и, таким образом, показали, что наше предположение о существовании M неверно. Таким образом, дополнение к останавливающемуся языку не может быть рекурсивно перечислимым.
Модели на основе параллелизма
Был разработан ряд вычислительных моделей на основе параллелизма, включая параллельную машину с произвольным доступом и Сеть Петри. Эти модели параллельных вычислений по-прежнему не реализуют никаких математических функций, которые не могут быть реализованы машинами Тьюринга.
Более сильные модели вычислений
Тезис Черча – Тьюринга предполагает, что не существует эффективной модели вычислений, которая могла бы вычислить больше математических функций, чем машина Тьюринга. Ученые-информатики придумали множество разновидностей гиперкомпьютеров, моделей вычислений, которые выходят за рамки вычислимости Тьюринга.
Бесконечное выполнение
Представьте себе машину, в которой каждый шаг вычислений требует половину времени, затрачиваемого на предыдущий шаг (и, надеюсь, половину энергии предыдущего шага...). Если мы нормализуем до 1/2 единицы времени количество времени, необходимое для первого шага (и до 1/2 единицы энергии - количество энергии, необходимое для первого шага...), для выполнения потребуется
$1 = ∑ п знак равно 1 ∞ 1 2 n знак равно 1 2 + 1 4 + 1 8 + 1 16 + ⋯ {\ displaystyle 1 = \ sum _ {n = 1} ^ {\ infty} {\ frac {1} {2 ^ {n }}} = {\ frac {1} {2}} + {\ frac {1} {4}} + {\ frac {1} {8}} + {\ frac {1} {16}} + \ cdots }$ $1 = \ sum _ {{n = 1}} ^ {{\ infty}} {\ frac {1} {2 ^ {n}}} = {\ frac {1} {2}} + {\ frac {1} {4}} + {\ frac {1} {8}} + {\ frac {1} {16}} + \ cdots$
единица времени (и 1 единица энергии...) для работы. Этот бесконечный ряд сходится к 1, что означает, что эта машина Zeno может выполнять счетное бесконечное количество шагов за 1 единицу времени (используя 1 единицу энергии...). Эта машина способна решить проблему остановки путем прямого моделирования работы рассматриваемой машины. В более широком смысле, любой сходящийся бесконечный [должен быть доказуемо бесконечным] ряд будет работать. Предполагая, что бесконечный ряд сходится к значению n, машина Зенона завершит счетное бесконечное выполнение за n единиц времени.
Машины Oracle
Так называемые машины Oracle имеют доступ к различным «оракулам», которые обеспечивают решение определенных неразрешимых проблем. Например, машина Тьюринга может иметь «останавливающийся оракул», который немедленно отвечает, остановится ли данная машина Тьюринга на заданном входе. Эти машины являются центральной темой исследования в теории рекурсии.
Пределы гипервычислений
Даже эти машины, которые, по-видимому, представляют собой предел автоматов, который мы могли вообразить, сталкиваются со своими собственными ограничениями. Хотя каждый из них может решить проблему остановки для машины Тьюринга, они не могут решить свою собственную версию проблемы остановки. Например, машина Oracle не может ответить на вопрос, остановится ли когда-либо данная машина Oracle.
См. Также
Ссылки
- Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. ISBN 0-534-94728-X. Часть вторая: Теория вычислимости, главы 3–6, стр. 123–222.
- Христос Пападимитриу ( 1993). Вычислительная сложность (1-е изд.). Эддисон Уэсли. ISBN 0-201-53082-1 .Глава 3: Вычислимость, стр. 57–70.
- S. Барри Купер (2004). Теория вычислимости (1-е изд.). Чепмен и Холл / CRC. ISBN 978-1-58488-237-4.