Недетерминированная машина тьюринга реферат

Обновлено: 02.07.2024

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

Цель этой статьи — представить некоторые фундаментальные основы вычислений. Если это окажется интересным, то в дальнейшем я могу написать более продвинутый топик на эту тему, но прямо сейчас я хочу просто рассмотреть логику простейшего абстрактного вычислительного устройства — машины с конечным числом состояний (finite state machine).

Машина с конечным числом состояний

Машина с конечным числом состояний (finite state machine, FSM), или конечный автомат (finite automaton) — это математическая абстракция, используемая при проектировании алгоритмов. Говоря простым языком, машина с конечным числом состояний умеет считывать последовательности входных данных. Когда она считывает входной сигнал, то переключается в новое состояние. Куда именно переключится, получив данный сигнал, — заложено в её текущем состоянии. Звучит запутанно, но на самом деле всё очень просто.

Представим устройство, которое читает длинную бумажную ленту. На каждом дюйме этой ленты напечатана буква — a или b.

Как только устройство считывает букву, оно меняет своё состояние. Вот очень простой граф переходов для такой машины:

Кружки — это состояния, в которых машина может быть. Стрелочки — переходы между ними. Так что, если вы находитесь в состоянии s и считываете a, то вам необходимо перейти в состояние q. А если b, то просто остаётесь на месте.

Итак, если изначально мы находимся в состоянии s и начинаем читать ленту из первого рисунка слева направо, то сначала будет прочитана a, и мы переместимся в состояние q, затем b — вернёмся обратно в s. Следующая b оставит нас на месте, а a вновь переместит в q. Элементарно, но какой в этом смысл?

Оказывается, если пропустить ленту с буквами через FSM, то по её итоговому состоянию можно сделать некоторые выводы о последовательности букв. Для приведённго выше простого конечного автомата финальное состояние s означает, что лента закончилась буквой b. Если же мы закончили в состоянии q, то последней на ленте была буква a.

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

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

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

Детерминированная машина с конечным числом состояний (Deterministic Finite State Machine)

Машины с конечным числом состояний, которые мы рассматривали выше, являются детерминированными. У них из любого состояния существует только один переход для любого разрешённого входного сигнала. Другими словами, не существует двух различных путей из данного состояния, когда вы считываете, допустим, букву a. На первый взгляд такое ограничение кажется глупым.

Что хорошего в наборе решений, если один и тот же сигнал на входе может переместить вас более, чем в одно состояние? Вы же не можете сказать компьютеру: если x == true , то выполни doSomethingBig() или doSomethingSmall(), не так ли?

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

Недетерминированная машина с конечным числом состояний (Nondeterministic Finite State Machine)

Недетерминированные машины с конечным числом состояний, или недетерминированные конечные автоматы (nondeterministic finite automaton, NFA) - это конечные автоматы, у которых входной сигнал для данного состояния может вести более чем в одно последующее состояние. Допустим, например, что мы хотим построить FSM, которая способна распознавать строки букв, начинающиеся с буквы a, за которой следует нуль или более букв b или нуль или более букв c. Условие останова - следующая буква алфавита на входе. Допустимыми строками будут:

Итак, надо распознать букву a с последующим нулём или более одинаковых букв b или c и с замыкающей следующей буквой алфавита. Самый простой способ отобразить этот алгоритм с помощью машины с конечным числом состояний представлен ниже. Финальное состояние t означает, что строка была принята целиком и соответствует шаблону.

Видите проблему? Находясь в начальной точке s мы понятия не имеем, какой из путей выбрать. Если мы прочли только букву a, то мы ещё не знаем, идти нам в q или в r. Существует несколько способов решить эту задачу. Первый из них - откат. Вы просто перебираете все возможные пути и игнорируете или возвращаетесь назад по тем из них, где решение заходит в тупик.

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

Другой путь - это преобразовать недетерминированную машину с конечным числом состояний в детерминированную. Существование алгоритма преобразования любой недетерминированного автомата в детерминированный является одним из интереснейших атрибутов NFA. Однако, часто это весьма сложный процесс. К счастью для нас, пример выше достаточно прост. Фактически, всё преобразование можно провести в уме, не прибегая к помощи формального алгоритма.

Машина ниже - детерминированная версия недетерминированной машины на предыдущем рисунке. Здесь конечные состояния t или v достижимы для любой принятой машиной строки.

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

Регулярные выражения

Если вы когда-нибудь занимались любым видом программирования, то вы почти наверняка сталкивались с регулярными выражениями (regular expressions). Регулярные выражения и машины с конечным числом состояний функционально эквивалентны. Всё, что можно допустить для (или связать с) регулярным выражением, можно допустить для (или связать с) конечным автоматом. Например, шаблон, который мы разбирали выше, можно связать с

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

ab
aabb
aaaaaabbbbbb
aaaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbb

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

Это положение известно как лемма о накачке для регулярных языков. Её основная мысль: если ваш шаблон имеет блок, который может быть повторён более, чем один раз, то этот шаблон не является регулярным. Другими словами, ни регулярные выражения, ни машины с конечным числом состояний не могут быть сконструированы так, чтобы распознавать все строки, которые можно связать с шаблоном.

Если вы посмотрите внимательнее, то заметите, что тип шаблона, в котором каждая a связана с b, выглядит очень похоже на HTML, где внутри любой пары тэгов можно заключить произвольное количество других пар тэгов. Вот почему вы можете использовать регулярное выражение или машину с конечным числом состояний для распознавания, содержит ли HTML-страница конкретные html , head и body элементы в правильном порядке, но не можете использовать регулярное выражение, чтобы сказать, является ли HTML-страница целиком корректной или нет. HTML - не регулярный шаблон.

Машина Тьюринга

Так как же нам распознавать нерегулярные шаблоны? Существует теоретическое устройство, подобное конечному автомату и называемое машиной Тьюринга (Turing Machine). Как и у машины с конечным числом состояний, у него имеется бумажная лента, с которой оно считывает информацию. Однако, машина Тьюринга также способна записывать и стирать данные на ленте. Полное объяснение принципов этого устройства займёт больше места, чем у нас здесь имеется, поэтому я обозначу лишь несколько важных моментов, относящихся к нашей дискуссии о машинах с конечным числом состояний и регулярных выражениях.

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

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

Почему это имеет значение?

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

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

Знание основ теории вычислительных систем позволяет вам брать проблему X, которую вы понятия не имеете как решать, и применять к ней подход: "Я не знаю, как решить X, но я знаю, как решить Y и как привести решение для Y к решению для X. Вот почему теперь я знаю, как решить X".

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

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

1. Описание машины Тьюринга

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

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

Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:

конечное множество состояний – Q, в которых может находиться машина Тьюринга;

конечное множество символов ленты – Г;

функция δ (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ gi) в тройку декартова произведения Q х Г х (машина переходит в состояние qi, заменяет символ gi на символ gj и передвигается влево или вправо на один символ ленты) – Q x Г-->Q х Г х

один символ из Г-->е (пустой);

подмножество Σ є Г — -> определяется как подмножество входных символов ленты, причем е є (Г — Σ);

одно из состояний – q0 є Q является начальным состоянием машины.

Решаемая проблема задается путем записи конечного количества символов из множества Σ є Г – Si є Σ на ленту:

после чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа (q0,w) –, после чего в соответствии с указанной функцией переходов (qi,Si) — ->(qj,Sk, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

Остановка машины происходит в том случае, если для пары (qi,Si) функция перехода не определена.

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

1.1 Свойства машины Тьюринга как алгоритма

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

Дискретность. Машина Тьюринга может перейти к (к + 1) — му шагу только после выполнения каждого шага, т.к именно каждый шаг определяет, каким будет (к + 1) — й шаг.

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

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

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

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

2. Сложность алгоритмов

Сложность алгоритма определяется вычислительными мощностями, необходимыми для его выполнения. Вычислительная сложность алгоритма часто измеряется двумя параметрами: Т (временная сложность) и S (пространственная сложность, или требования к памяти). И Т, и S обычно представляются в виде функций от n, где n — это размер входных данных. (Существую и другие способы измерения сложности: количество случайных бит, ширина канала связи, объем данных и т.п.)

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

Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему памяти. Например, если Т= О(n), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т=О(2n), то добавление одного бита к входным данным удвоит время выполнения алгоритма.

Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от n: 0(1). Алгоритм является линейным, если его временная сложность О(n). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы — полиномиальны, их сложность — О(m), где m — константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем

Алгоритмы, сложность которых равна О(tf(n)), где t — константа, большая, чем 1, a f(n) — некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна О(сf(n)), где где с — константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным.

С ростом n временная сложность алгоритмов может стать настолько огромной, что это повлияет на практическую реализуемость алгоритма.

При условии, что единицей времени для нашего компьютера является микросекунда, компьютер может выполнить постоянный алгоритм за микросекунду, линейный — за секунду, а квадратичный — за 11.6 дня. Выполнение кубического алгоритма потребует 32 тысяч лет, что в принципе реализуемо, компьютер, конструкция которого позволила бы ему противостоять следующему ледниковому периоду, в конце концов получил бы решение. Выполнение экспоненциального алгоритма тщетно, независимо от экстраполяции роста мощи компьютеров, параллельной обработки или контактов с инопланетным суперразумом.

Взглянем на проблему вскрытия алгоритма шифрования грубой силой. Временная сложность такого вскрытия пропорциональна количеству возможных ключей, которое экспоненциально зависит от длины ключа. Если n — длина ключа, то сложность вскрытия грубой силой равна 0(2n). Сложность вскрытия грубой силой при 56-битовом ключе составляет 256, а при 112-битовом ключе — 2112. В первом случае вскрытие возможно, а во втором — нет.

2.1 Сложность проблем

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

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

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

P NP (или P=NP). Однако, большинство специалистов, занимающихся теорией сложности, убеждены, что это классы неравны.

Как ни странно, можно доказать, что некоторые NP-задачи настолько же трудны, что и любая задача этого класса. Такие задачи называются NP-полными. То есть, если такая задача решается за полиномиальное время, то P=NP.

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

Наконец, существует класс задач EXPTIME. Эти задачи решаются за экспоненциальное время. В настоящее время можно доказать, что EXPTIME-полные задачи невозможно решить за детерминированное полиномиальное время. Кроме того, доказано, что P<>EXPTIME.

3. Машина Тьюринга и алгоритмически неразрешимые проблемы

За время своего существования человечество придумало множество алгоритмов для решения разнообразных практических и научных проблем. Зададимся вопросом – а существуют ли какие-нибудь проблемы, для которых невозможно придумать алгоритмы их решения?

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

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

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

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

а) Отсутствие общего метода решения задачи

Проблема 1: Распределение девяток в записи числа;

Определим функцию f(n) = i, где n – количество девяток подряд в десятичной записи числа, а i – номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5.

Задача состоит в вычислении функции f(n) для произвольно заданного n.

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

Проблема 2: Вычисление совершенных чисел;

Определим функцию S(n) = n-ое по счёту совершенное число и поставим задачу вычисления S(n) по произвольно заданному n. Нет общего метода вычисления совершенных чисел, мы даже не знаем, множество совершенных чисел конечно или счетно, поэтому наш алгоритм должен перебирать все числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос о останове алгоритма. Если мы проверили М чисел при поиске n-ого совершенного числа – означает ли это, что его вообще не существует?

Проблема 3: Десятая проблема Гильберта;

Пусть задан многочлен n-ой степени с целыми коэффициентами – P, существует ли алгоритм, который определяет, имеет ли уравнение P=0 решение в целых числах?

Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам.

б) Информационная неопределенность задачи

Проблема 4: Позиционирование машины Поста на последний помеченный ящик;

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

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

в) Логическая неразрешимость (в смысле теоремы Гёделя о неполноте)

Проблема 6: Проблема эквивалентности алгоритмов;

По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных.

Проблема 7: Проблема тотальности;

По произвольному заданному алгоритму определить, будет ли он останавливаться на всех возможных наборах исходных данных. Другая формулировка этой задачи – является ли частичный алгоритм Р всюду определённым?

Заключение

Список литературы

1. Рощин А.Г., Половов Р.М. Теория автоматов. Часть I. Тексты лекций — Москва: МГТУ ГА, 2001. — 76 с.

В теоретической информатике , недетерминирован машин Тьюринга ( НТМ ) теоретическая модель вычислений , чьи регулирующие правила определяют более чем один из возможных вариантов действий , когда в некоторых конкретных ситуациях. То есть следующее состояние NTM не полностью определяется его действием и текущим символом, который он видит, в отличие от детерминированной машины Тьюринга .

НТМ иногда используются в мысленных экспериментах для проверки возможностей и ограничений компьютеров. Одной из наиболее важных открытых проблем теоретической информатики является проблема P и NP , которая (среди других эквивалентных формулировок) касается вопроса о том, насколько сложно моделировать недетерминированные вычисления с помощью детерминированного компьютера.

СОДЕРЖАНИЕ

Детерминированная машина Тьюринга

В детерминированной машине Тьюринга (DTM) набор правил предписывает не более одного действия, которое должно быть выполнено для любой данной ситуации.

Детерминированная машина Тьюринга имеет функцию перехода, которая для данного состояния и символа под головкой ленты определяет три вещи:

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

Например, X на ленте в состоянии 3 может заставить DTM записать Y на ленте, переместить головку на одну позицию вправо и переключиться в состояние 5.

Интуиция

В отличие от детерминированной машины Тьюринга, в недетерминированной машине Тьюринга ( NTM ) набор правил может предписывать более одного действия, которое должно быть выполнено для любой данной ситуации. Например, X на ленте в состоянии 3 может позволить NTM:

Напишите Y, двигайтесь вправо и переключитесь в состояние 5

Напишите X, двигайтесь влево и оставайтесь в состоянии 3.

Разрешение нескольких правил

Определение

Недетерминированную машину Тьюринга можно формально определить как набор из шести элементов , где M знак равно ( Q , Σ , ι , ⊔ , А , δ )

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

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

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

Альтернативные определения

В качестве математической конструкции, используемой в основном в доказательствах, существует множество незначительных вариаций определения NTM, но все эти вариации допускают эквивалентные языки.

Движение головы в выходных данных отношения перехода часто кодируется численно вместо использования букв для обозначения перемещения головы влево (-1), неподвижно (0) и вправо (+1); давая выход функции перехода . Обычно опускают стационарный (0) выход и вместо этого вставляют транзитивное замыкание любых желаемых стационарных переходов. ( Q × Σ × < - 1 , 0 , + 1 >) \ right)>

Некоторые авторы добавляют явное состояние отклонения , которое заставляет NTM останавливаться без принятия. Это определение по-прежнему сохраняет асимметрию, которую может принять любая недетерминированная ветвь, но каждая ветвь должна отклонить, чтобы строка была отклонена.

Вычислительная эквивалентность с DTM

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

DTM как частный случай NTM

NTM включают DTM как особые случаи, поэтому каждое вычисление, которое может быть выполнено с помощью DTM, также может выполняться эквивалентным NTM.

ЦМР моделирование НТМ

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

Множественность состояний конфигурации

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

Кратность лент

Другая конструкция имитирует NTM с 3-ленточными DTM, из которых первая лента всегда содержит исходную входную строку, вторая используется для моделирования конкретного вычисления NTM, а третья кодирует путь в дереве вычислений NTM. ЦММ с тремя лентами легко моделируются с помощью обычного ЦММ с одной лентой.

Сложность времени и P по сравнению с NP

Во второй конструкции построенный DTM эффективно выполняет поиск в ширину дерева вычислений NTM, посещая все возможные вычисления NTM в порядке увеличения длины, пока не найдет принимающее. Следовательно, длина принимающего вычисления DTM, как правило, экспоненциальна от длины самого короткого принимающего вычисления NTM. Считается, что это общее свойство моделирования NTM с помощью DTM. Проблема P = NP , самый известный нерешенный вопрос в информатике, касается одного случая этой проблемы: обязательно ли каждая проблема, решаемая с помощью NTM за полиномиальное время, также может быть решена с помощью DTM за полиномиальное время.

Ограниченный недетерминизм

НТМ обладает свойством ограниченного недетерминизма. То есть, если NTM всегда останавливается на данной входной ленте T, то он останавливается за ограниченное количество шагов и, следовательно, может иметь только ограниченное количество возможных конфигураций.

Сравнение с квантовыми компьютерами

Предполагаемая форма круга задач, решаемых квантовыми компьютерами за полиномиальное время (BQP). Обратите внимание, что на рисунке предполагается и . Если это не так, то фигура должна выглядеть иначе. п ≠ N п > \ neq >> N п ≠ п S п А C E <\ Displaystyle > \ neq >>

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

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

Определим класс NP в терминах недетерминированной машины Тьюринга.

НТ осуществляет работу в 2 этапа:

Стадия 1 — угадывание. На ленте машины записано слово a(I) в алфавите А, т.е. код задачи I, начиная с некоторой ячейки с номером 1 слева направо. Левее – в ячейке с номером 0 — записана разделяющая *.

Угадывающий модуль, просматривая ячейку за ячейкой слово a(I), идет влево от разделительной ячейки и по одному символу за такт записывает слово c(I). Если угадывающий модуль останавливается, то происходит переход ко второй стадии работы НТ. При этом имеем конфигурацию: c(I)*q₁a(I). (1)

Стадия 2 — решение. На этой стадии НТ работает, как обычная машина Тьюринга с начальной конфигурацией (1). Если машина через конечное число шагов придет в состояние q_y_, то говорят, что она принимает конфигурацию (1).

Определение 2. Говорят, что недетерминированная машина Тьюринга НТ принимает слово a(I), если существует слово c(I)такое, что конфигурация c(I)*q₁a(I) принимается НТ.

Определим время работы НТ: , если a(I) принимается, где t₁(I) — время работы на стадии 1, т.е. t₁(I)=|c(I)|, t₂(I) — время работы на стадии 2, т.е. t₂(I)=t_T(c(I)* a(I)), где T — соответствующая (обычная) машина Тьюринга.

Определим время работы НТ как функцию натурального аргумента

Определение 3. Говорят, что недетерминированная машина Тьюринга НТ решает массовую задачу П за полиномиальное время, если t_HT(n)=O(p(n)) для некоторого полинома р. Другими словами, недетерминированная машина Тьюринга НТ решает массовую задачу П за полиномиальное время, если время её работы ограничено сверху полиномом от длины входа.

Очевидно, что PÍNP.

Теорема. Если задача П NP, то существует полином р(n) такой, что П может быть решена с помощью детерминированного алгоритма со сложностью О(2 р( n) ), где n – размер задачи П.

26. Ещё один подход к определению класса NP. Примеры недетерминированных алгоритмов. О проблеме P¹NP.

Определим NP как класс всех задач, которые можно решить недетерминированными алгоритмами, работающими в течение полиномиального времени, т.е. недетерминированными алгоритмами, в которых всегда есть путь успешного вычисления за время, полиномиальное относительно длины входной строки; очевидно P Í NP. Поскольку путей вычисления может быть экспоненциально много, вероятно, что алгоритмы, допустимые в этом случае, намного сильнее, чем детерминированные алгоритмы, допустимые для задач из P. Например, задача входит в NP, если она может быть решена недетерминированным алгоритмом поиска с возвращением (алгоритм 26.1), в котором

2) длина каждого пути вычисления ограничена полиномом относительно длины входной строки.

while S_k ¹ Æ do

[ не приводит к решению]

Алгоритм 26.1.Недетерминированный общий алгоритм поиска с возвращением для определения, имеет ли задача решение.

while S ¹ Æ do

if cost £ then успех

else неудача

Алгоритм 26.2. Полиномиально ограниченный недетерминированный алгоритм для определения, имеет ли задача коммивояжера с n городами ( представленная матрицей расстояний между городами n-го порядка)решение стоимости не больше b.

Для того чтобы продемонстрировать силу полиномиально ограниченных недетерминированных алгоритмов и, следовательно, широту класса NP, мы покажем, что некоторый вариант задачи коммивояжера входит в NP. Если задана n´n матрица С расстояний между городами в задаче коммивояжера с n городами, то легко видеть, что алгоритм 22.1 можно модифицировать и получить полиномиально ограниченный недетерминированный алгоритм для определения, существует ли для любой границы b какой – либо маршрут стоимости не больше b; таким алгоритмом является алгоритм 26.2.

27. Примеры задач класса NP.

Опасности нашей повседневной жизни: Опасность — возможность возникновения обстоятельств, при которых.

ГОСТ

Машина Тьюринга — это абстрактный исполнитель или абстрактная вычислительная машина.

Введение

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

Эта научная работа послужила стимулом к более углублённому изучению цифрового исчисления и компьютерных устройств, в том числе осознание мысли, что есть проблематика в сфере вычислений, которую нельзя решить на обычных электронных вычислительных машинах пользователей

Машина Тьюринга

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

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

Готовые работы на аналогичную тему

Машина осуществляет связь двух конечных рядов информационных данных, а именно алфавит знаков на входе $A = (a_0, a_1, …, a_m)$ и алфавит состояний $Q = (q_0, q_1, . q_p)$. Пассивным считается состояние $q_0$. Предполагается, что машина прекращает выполнение операций, когда считывает именно его. Исходным состоянием является состояние $q_1$, и устройство запускается в работу, когда считывает это стартовое состояние. Слово на ленте, которое является входной информацией, расположено последовательно по одной букве в позиции. При этом, впереди него и за ним расположены нулевые квадраты.

Принцип работы машины Тьюринга

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

Записать в текущую ячейку нужный знак.
Выполнить смену текущего состояния.
Переместиться в заданную сторону вдоль ленты.

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

Свойство дискретности. Цифровое устройство выполняет переход к очередному этапу n+1 лишь после полного завершения предыдущего. Каждый завершенный шаг определяет, каким будет следующий.
Свойство понятности. Машина осуществляет лишь одну операцию для выбранной ячейки. Она записывает алфавитный символ и выполняет одно перемещение в указанную сторону.
Свойство детерминированности. Всем позициям в машине сопоставляется только один вариант осуществления задаваемой схемы, и на всех шагах операции и их очерёдность осуществления строго определены.
Свойство результативности. Окончательный итог на каждом шаге вычисляет машина Тьюринга. Программа работает согласно заданному алгоритму и за не бесконечное количество выполненных этапов доходит до состояния $q_0$.
Свойство массовости. Каждой машине сопоставлен набор допустимых слов, которые входят в алфавит.

Функции машины Тьюринга

Рисунок 1. Функции машины Тьюринга. Автор24 — интернет-биржа студенческих работ

Программа для машины Тьюринга

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

Читайте также: