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

Все-таки я не понимаю, как именно они «выбирают». Например, для палиндорм каждый источник, который я нашел, просто говорит, что автомат «угадывает» середину слова. Что это обозначает?

Я могу думать о нескольких возможных значениях:

1. Он входит в одно состояние случайно и поэтому может не принять слово, которое на самом деле в языке

2. Он каким-то образом идет «всеми возможными способами», поэтому, если первый из них неверен, он проверяет, может ли любой другой быть правильным

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

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

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

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

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

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

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

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

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

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

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

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

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

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

«Гадание» напрямую связано с нашей экзистенциальной интерпретацией недетерминизма

В двух словах: эта идея, которую недетерминированный автомат может угадать (или ей поможет оракул), напрямую связана с нашей экзистенциальной интерпретацией недетерминизма. Возможна другая интерпретация (возможно, другие), где «гадание» не имеет смысла.

Недетерминизм странный. У нас есть один способ интерпретации этого в теории автоматов, но априори не очевидно, как мы должны это делать.

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

Есть много способов объединить то, что уже известно, с правилами вывода, чтобы получить новые результаты. И ситуация обычно такая же, если мы пытаемся восстановить доказательство в обратном направлении от результата.

Пытаясь решить такую ​​проблему, мы пытаемся « угадать » путь в какой-то переходной системе.

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

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

$DC$$A$$A$$A$

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

$R$$w$ тогда и только тогда есть одно вычисления , которое останавливает и принять . Это согласуется с нашим собственным взглядом на недетерминированный процесс доказательства, который считается успешным, если он может идентифицировать одно дерево доказательств для доказательства теоремы.

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

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

Тем не менее, можно также интерпретировать недетерминизм универсальным способом, как: говорят, что распознаватель (универсально) принимает ввод "w", если все возможные вычисления останавливаются и принимают ввод.Это универсальное принятие соответствует концепции универсальной остановки, введенной в том же ответе.

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

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

Обратите внимание, что эта идея угадывания была бы бессмысленной в универсальной интерпретации принятия.