Почему недетерминизм является полезным понятием?

23

Автомат - это абстрактная модель цифрового компьютера. Цифровые компьютеры полностью детерминированы; их состояние в любое время однозначно предсказуемо из входных данных и исходного состояния.

Когда мы пытаемся моделировать реальные системы, зачем включать недетерминизм в теорию автоматов?

tanmoy
источник
1
Возможно, было бы полезно спросить, кто первоначально описал НТМ и какова их цель / цель в то время.
Усул
2
Обратите внимание, что тот факт, что машина является детерминированной, не всегда означает, что наш код таков. Любой, кто делал многозадачность / многопоточность, может засвидетельствовать тот факт, что время, в которое происходит переключение задач, часто непредсказуемо в любых практических терминах, и мы должны разработать явные блокировки, чтобы их поведение выглядело детерминированным. (По сути, в состоянии есть скрытые переменные.) Связь поднимает ту же проблему. Я, честно говоря, не знаю, помогают ли NDA справиться с этими проблемами - я инженер-программист, а не специалист по компьютерам, - но в реальном мире ваша предпосылка чрезмерно оптимистична.
Кешлам
Когда вы говорите о многопоточности, возможно, у вас есть недетерминизм, по крайней мере, если вы рассматриваете металл и ОС для формирования машины. Что смешно, так это то, что сам код является детерминированным.
Рафаэль
@ Raphael, @keshlam Другими словами, мы можем сказать, что «недетерминированные модели также полезны для симуляции параллельного выполнения кода»
Грижеш Чаухан,
@keshlam Я добавил вашу точку зрения в своем ответе, @ Tanmoy прочитал обновил мой ответ.
Грижеш Чаухан

Ответы:

16

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

(01)*01(0 + 1)*  

Теперь предположим, что если вас попросят нарисовать DFA для языка, созданного выше RE.

С моим знанием проектирования ассоциаций, я знаю , что (1) , когда *присутствует в регулярном выражении показала мне нужно соответствующее цикл в FA (2) Соединить операции как a.bсредство что - то вроде: .(q0)─a→(q1)─b→(q2)

Итак, с первой попытки я бы нарисовал NFA как:

инжир

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

  1. Цикл в состоянии q 0 должен быть для(01)*
  2. 01(после (01)*) дает(q0)─0→(q1)─1→(q2)
  3. (0 + 1)* дает сам цикл в состоянии q 2 для метки 0, 1

В соответствии с моей аналогией, я думаю, что ФА, который я нарисовал выше, сравнительно просто извлечь из данного RE. И, к счастью, в классе конечных автоматов каждая недетерминированная модель может быть преобразована в эквивалентную детерминированную. У нас есть алгоритмический метод для преобразования NFA в DFA . Так что я могу легко конвертировать выше NFA в DFA:

Рис-2

Другая часть , к сожалению , это не всегда возможно преобразовать недетерминированное модель в детерминированный, например , класс для детерминированной толчке вниз автомата является подмножество класса детерминированных стекового автомата «проверить диаграмму Венна » , и вы не всегда можете конвертировать NPDA в КПК.

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

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

Здесь я также хотел бы процитировать из Википедии Использование недетерминированного алгоритма :

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

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

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

Я бы также предложил вам прочитать следующие ссылки:
1. В чем разница между недетерминизмом и случайностью?
2. 9.2.2. Недетерминированные и вероятностные модели: (а). Недетерминированный: я понятия не имею, что сделает природа. (б). Вероятностный: я наблюдал за природой и собирал статистику.
3. Недетерминированное программирование

Грижеш Чаухан
источник
@Grijest: большое спасибо за такую ​​огромную разработку. Единственное недоразумение: «Противоположно детерминированные модели лучше представляют эффективные, минимизированные и менее избыточные решения». - Но я думаю, что детерминированные модели менее эффективны, чем недетерминированные. (Вот почему проблемы NP более сложны, чем П. Не так ли?)
tanmoy
@tan На самом деле использование слова «эффективный» неверно, и да, вы правы, что недетерминированные модели более эффективны, чем детерминированные. Класс задач, охватываемых детерминированными моделями, является подмножеством недетерминированной модели.
Грижеш Чаухан
Так в каком контексте детерминированные модели являются «эффективными», чем недетерминированные (как вы упомянули)?
танмой
@tan Предположим, если вы хотите выполнить дальнейшую операцию (например, хотите преобразовать FA в RE, или объяснить доказательство прокачки леммы, или какой-то другой ..), тогда детерминистическая модель даст вам лучшие результаты (поэтому я сказал, что это эффективно).
Грижеш Чаухан
@tan Вы понимаете неоднозначные грамматики?
Грижеш Чаухан
9

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

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

vonbrand
источник
Я думаю, что первая часть вашего ответа на самом деле неверна. Как вы думаете, почему автоматы возникли первыми? И DFA, и NFA были определены через 10+ лет после определенных Тьюрингом ТМ. Смотрите обсуждение по этой теме
Артем Казнатчеев
@ArtemKaznatcheev, модель машины Тьюринга является автоматом, и она определенно предшествует компьютерам, по крайней мере, на десятилетие.
vonbrand
да, но когда люди говорят автоматы, они не имеют в виду ТМ, но они имеют в виду автоматы конечного состояния и их прямые расширения (КПК, NPDA и т. д.). Посмотрите на вопрос, который я связал для истории, и вы увидите, что как ТМ, так и архитектура фон Неймана были разработаны независимо от того, что мы сейчас называем теорией автоматов.
Артем Казнатчеев
4
@ArtemKaznatcheev, DFA / NFA, PDA, LBA, TM - все это автоматы. Как и преобразователи (FA с выходом, PDA с выходом).
vonbrand
1
Последний абзац неверен. Пролог предшествует GCL, и даже все еще существует и довольно широко распространен. Пролог, конечно, не был разработан в вакууме, опираясь на предыдущие недетерминированные языки программирования, такие как PLANNER. Вероятно, заслуга Голомба и Баумерта в «Программе возврата» с 1965 года.
Псевдоним
7

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

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

Юваль Фильмус
источник
понимая ваш ответ, но не понимая его должным образом. Не могли бы вы уточнить, как легко можно построить блок питания, используя недетерминизм?
Танмой
«Недетерминизм также важен для сложности вычислений, где он используется для определения класса NP». - это подтверждает важность недетерминизма только в том случае, если мы предполагаем, что NP является полезным понятием, а только если недетерминизм полезен.
Рафаэль
@Raphael NP-полнота является важной концепцией, независимо от вашей позиции по поводу недетерминизма.
Юваль Фильмус
2
@Tanmoy Если у вас есть недетерминизм, вам не нужна конструкция powerset, но, к сожалению, реальные компьютеры являются детерминированными. Тем не менее, может быть проще имитировать NFA напрямую, чем сначала преобразовывать его в DFA. Проверьте ответ, на который я ссылаюсь, для более подробной информации.
Ювал Фильмус
4

Вы правильно утверждаете, что автоматы являются моделями, поэтому недетерминизм может иметь две части:

  1. Использовать при моделировании реальных задач.

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

  2. Используйте в теории.

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

Рафаэль
источник
4

(Это переформулировка некоторых других ответов, но я все равно выложу :)

Вы пишете: автомат - это абстрактная модель цифрового компьютера.

Я не согласен! Автоматы моделируют то, как мы, люди, определяем вычисления, а не только то, как их выполняют компьютеры. Недетерминизм как раз и есть разница. Наши спецификации часто недетерминированы.

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

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

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

reinierpost
источник
2

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

Массимо Кафаро
источник
Без контекста и детерминированного без контекста?
Альт
@alto А как насчет этого?
Бабу
@babou Я пытался указать, что «недетерминизм не является чем-то более сильным, чем детерминизм», это ложное утверждение. NPDA являются более мощными, чем КПК.
Альт
1
@alto: нет, вы неправильно поняли это утверждение. С точки зрения вычислимости они полностью эквивалентны, поскольку класс задач (или языков, если вы предпочитаете), которые вы можете решить НЕЗАВИСИМО от того, сколько вычислительных ресурсов требуется, одинаков. И действительно, вы МОЖЕТЕ симулировать недетерминированную машину с помощью детерминированной. Опять же, требуемое время и пространство не имеет значения в контексте вычислимости.
Массимо Кафаро
1
@MassimoCafaro Не могу согласиться больше, в теории. На практике кажется, что я предпочитаю спорить о семантике.
альт
2

изобретение машины Тьюринга было сделано в 1936 году Тьюрингом. FSM-подобные модели были представлены МакКаллохом и Питтсом , двумя нейрофизиологами, в качестве модели для нейробиологической активности в 1943 году со страницы истории Stanford CS :

Захватывающая история того, как конечные автоматы стали отраслью компьютерных наук, иллюстрирует их широкий спектр применений. Первые люди, которые рассмотрели концепцию конечного автомата, включали команду биологов, психологов, математиков, инженеров и некоторых из первых компьютерных ученых. У всех них был общий интерес: моделировать мыслительный процесс человека, будь то мозг или компьютер. Уоррен МакКаллох и Уолтер Питтс, два нейрофизиолога, были первыми, кто представил описание конечных автоматов в 1943 году. Их работа под названием «Логическое исчисление, имманентное нервной деятельности», внесла значительный вклад в изучение теории нейронных сетей, теории автоматы, теория вычислений и кибернетика. Позже, два ученых-компьютерщиков, Г.Х. Мили и Э. Ф. Мур, обобщил теорию на гораздо более мощные машины в отдельных работах, опубликованных в 1955-56 гг. Конечные автоматы, машина Мили и машина Мура, названы в знак признания их работы.

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

ВЗН
источник
3
Эй, я видел ваш профиль и выглядит так, как будто кто-то намеренно понижает ваши ответы (каждый раз, когда у вас есть только два отрицательных голоса) ... Этот ответ не ошибочный , ответ добавляет полезную информацию. +1
Грижеш Чаухан
0

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

На самом деле у меня была путаница, связанная с механизмом недетерминированной модели. Я всегда задавался вопросом о недетерминированной машине, поскольку это немеханическая машина, которой нет в реальном мире. Я всегда сравнивал Automata с нашими современными компьютерами, которые по своей природе являются полностью детерминированными. На самом деле я не совсем правильно понимал недетерминированную модель. Теперь я думаю, что хорошо понимаю недерминистскую модель: недетерминированная машина - это машина, которая всегда следует по пути выполнения, который приводит к принятию строки (без обратного отслеживания). Но как это может быть возможно в реальной жизни? : Для современных компьютеров абсолютно невозможно быть таким умным, чтобы предсказывать будущее. Так почему вообще недетерминизм? Ответ на этот вопрос довольно сложный. Из этого я пришел к выводу, что: Теория автоматов существовала, когда компьютеров не существовало (сначала теория, а потом практическая). Это чисто теоретический предмет, а понятие недетерминизма пришло интуитивно. Мотивом предмета «Теория автоматов» было не то, чтобы иметь дело с практическими компьютерами. Но когда практически компьютер приходит, то с помощью теории автоматов мы можем точно определить практические компьютеры: каковы ограничения современных компьютеров. Какие алгоритмические проблемы очень сложны для компьютеров и настолько непрактичны (Здесь роль недерминизма очень важна, поэтому можно различить два класса сложности P и NP). Каковы решения этих непрактичных задач, с помощью которых он может быть выполнен сравнительно быстрее? Это полезность недетерминизма. Это чисто теоретический предмет, а понятие недетерминизма пришло интуитивно. Мотивом предмета «Теория автоматов» было не то, чтобы иметь дело с практическими компьютерами. Но когда практически компьютер приходит, то с помощью теории автоматов мы можем точно определить практические компьютеры: каковы ограничения современных компьютеров. Какие алгоритмические проблемы очень сложны для компьютеров и настолько непрактичны (Здесь роль недерминизма очень важна, поэтому можно различить два класса сложности P и NP). Каковы решения этих непрактичных задач, с помощью которых он может быть выполнен сравнительно быстрее? Это полезность недетерминизма. Это чисто теоретический предмет, а понятие недетерминизма пришло интуитивно. Мотивом предмета «Теория автоматов» было не то, чтобы иметь дело с практическими компьютерами. Но когда практически компьютер приходит, то с помощью теории автоматов мы можем точно определить практические компьютеры: каковы ограничения современных компьютеров. Какие алгоритмические проблемы очень сложны для компьютеров и настолько непрактичны (Здесь роль недерминизма очень важна, поэтому можно различить два класса сложности P и NP). Каковы решения этих непрактичных задач, с помощью которых он может быть выполнен сравнительно быстрее? Это полезность недетерминизма. Но когда практически компьютер приходит, то с помощью теории автоматов мы можем точно определить практические компьютеры: каковы ограничения современных компьютеров. Какие алгоритмические проблемы очень сложны для компьютеров и настолько непрактичны (Здесь роль недерминизма очень важна, поэтому можно различить два класса сложности P и NP). Каковы решения этих непрактичных задач, с помощью которых он может быть выполнен сравнительно быстрее? Это полезность недетерминизма. Но когда практически компьютер приходит, то с помощью теории автоматов мы можем точно определить практические компьютеры: каковы ограничения современных компьютеров. Какие алгоритмические проблемы очень сложны для компьютеров и настолько непрактичны (Здесь роль недерминизма очень важна, поэтому можно различить два класса сложности P и NP). Каковы решения этих непрактичных задач, с помощью которых он может быть выполнен сравнительно быстрее? Это полезность недетерминизма. Каковы решения для этих непрактичных проблем, с помощью которых это может быть выполнено сравнительно быстрее? Это полезность недетерминизма. Каковы решения для этих непрактичных проблем, с помощью которых это может быть выполнено сравнительно быстрее? Это полезность недетерминизма.

Пожалуйста, поправьте меня, если что-то не так.

tanmoy
источник
Неверно утверждать, что недетерминированная машина - это машина, которая всегда следует по пути исполнения, который приводит к принятию строки . Это не делает этого! Недетерминированная машина - это машина, чья операция позволяет делать некоторые непреднамеренные (= недетерминированные) выборы во время выполнения. В таких машинах нет ничего нереального, например, они могут попросить окружающую среду сделать такой выбор. Эти машины затем применяются к задачам, для которых определено, что определенные варианты выбора приводят к принятию.
reinierpost
@reinierpost: Итак, вы говорите, что недетерминированные машины существуют в реальной жизни.
tanmoy
Да. Вот пример: предположим, что вы за рулем автомобиля, и вы не принимаете никаких решений относительно маршрута, по которому будете следовать. Например, вы можете бесцельно разъезжать или брать указания от человека-навигатора или навигационного устройства. Автомобиль, а вы недетерминированная система для поездок по местам. Вы движетесь через движение и продолжаете сталкиваться с выбором, в каком направлении идти. Для вас и машины эти выборы недетерминированы: вы не решаете, в каком направлении двигаться, но, учитывая это решение, вы будете следовать ему.
reinierpost
@reinierpost: существует ли какой-либо недетерминированный компьютер? Мой ответ - НЕТ. потому что, если он существует, то проблемы NP будут иметь сложность за полиномиальное время. не так ли?
танмой
Являются ли компьютеры детерминированными или недетерминированными, зависит от того, как вы на них смотрите. Когда компьютер останавливается и ждет, когда пользователь что-то сделает, и его последующие действия будут зависеть от того, что пользователь делает, вы можете сказать, что это недетерминированный выбор. Нет, это не значит, что P = NP.
reinierpost
0

Недетерминизм полезен, потому что он помогает вам понять детерминизм, но не наоборот. Вы могли бы сказать, что недетерминизм - большая идея. Детерминированная машина Тьюринга является частным случаем недетерминированного. - Недетерминизм может помочь нам понять, почему на современных платформах трудно определить некоторые проблемы. Существует ряд вычислительных задач, которые не имеют эффективного решения на детерминированной вычислительной платформе, но мы понимаем, что на недетерминированных могут быть эффективные решения. ... состояние, кодировка, недетерминизм, все они связаны http://people.cs.umass.edu/~rsnbrg/teach-eatcs.pdf

В детерминированной машине Тьюринга набор правил предписывает не более одного действия, которое должно быть выполнено для любой конкретной ситуации. Недетерминированная машина Тьюринга (NTM), напротив, может иметь набор правил, которые предписывают более одного действия для данной ситуации. http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Если вы можете создать программный блок, который может управлять переходами состояний настолько хорошо, что он может обрабатывать более одного действия, вы можете получить производительность за пределами детерминированных машин.

Том
источник
Я не уверен, что предполагаемые ссылки на реальность вообще полезны. Совершенно очевидно, что мы не можем построить недетерминированную машину (по крайней мере, сегодня), поэтому это полностью теоретическая конструкция.
Рафаэль
Мы можем построить недетерминированную машину, позволяя принимать недетерминированные решения чем-то внешним по отношению к машине.
reinierpost
@ reinierpost, что более важно, мы можем строить недетерминированные машины как детерминированные, не подвергаясь экспоненциальным накладным расходам. см. теорему Савича. ru.wikipedia.org/wiki/Savitch's_theorem
Том
@ Рафаэль, некоторые ссылки на реальный мир важны. Почему кеширование работает? Потому что события в реальном мире, который в конечном итоге является источником всех данных, происходят по нормальному распределению. см. временную местность: durablescope.blogspot.co.at/2009/11/…
Том
@ reinierpost, и что-то внешнее - это то, что Тьюринг назвал оракулом. Я думаю, вы можете подумать, если это как данные, поступающие из кеша или что-то вроде многолинейной машины или даже доступ к оперативной памяти.
Том
0

Почему недетерминизм полезен понятию?

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

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

Томас Климпел
источник
Можете ли вы привести конкретный пример? Мне трудно понять, что вы подразумеваете здесь под «симметрией».
Рафаэль
@Raphael Как насчет обращения (01) * 01 (0 + 1) * к (0 + 1) * 10 (10) * так, чтобы оно распознавало обратную входную строку, и применяет эту симметрию к недетерминированной машине, обращая все стрелка и поменять местами начальное и конечное состояние? Я не уверен, есть ли значительно более интересные примеры для конечных автоматов, но я мог бы попытаться придумать интересный пример для КПК.
Томас Климпел
Я написал о своем ответе на аналогичный вопрос в блоге об Обратимости бинарных отношений, субстохастических матриц и частичных функций .
Томас Климпел