В чем разница между недетерминизмом и случайностью?

38

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

Я чувствую, как будто я понимаю, но я действительно не понимаю. Может ли кто-нибудь объяснить мне это (в контексте машин или вообще)?

Изменить 1:
Просто чтобы уточнить, цитата была в контексте конечного автомата, но вопрос имеет значение для машин Тьюринга также, как другие ответили.

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


источник
5
В информатике люди иногда используют термин «детерминистический», чтобы подчеркнуть, что алгоритм не рандомизирован. Отсюда путаница: детерминированный означает нерандомизированный, но недетерминированный не означает рандомизированный.
Юкка Суомела
Этот вопрос приводит меня в этот угол SE ...
Трой Ву

Ответы:

27

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

2N

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

Kurt
источник
Курт, не могли бы вы объяснить, как была получена цифра 2 ^ N. Если для каждой ветви есть 2 возможности и есть N таких этапов, чтобы достичь решения, разве это не сделает его 2 ^ (N + 1) -1. Я пытаюсь думать об этом как о графике, и я могу ошибаться. Не могли бы вы объяснить, как вы пришли к 2 ^ N числа. Спасибо.
Гангадхар
Что ж, если вы представляете вычисления в виде дерева с корнем, представляющим начальную конфигурацию как шаг 0, то после N шагов у вас будет 2 ^ N листьев, и то, что я называю ветвью, - это путь от корня к лист. Это правда, что у вас будет 2 ^ (N + 1) -1 узлов, представляющих все возможные конфигурации в какой-то момент вычисления. Я надеюсь, что моя терминология в порядке!
Курт
Все науки используют одно и то же определение недетерминизма, объединенного понятием неограниченной энтропии. Непредсказуемые результаты во всех науках связаны с невозможностью априори перечислять все возможные выходные данные алгоритма (или системы), поскольку он принимает неограниченные состояния, то есть класс сложности NP. Указание конкретного входа для наблюдения за тем, останавливается ли он, и отметка, что результат идемпотентен, эквивалентен в других науках поддержанию постоянной энтропии вселенной постоянной, повторяя то же самое изменение состояния. Вычислительная техника позволяет эту энтропийную изоляцию, а естественные науки - нет.
Шелби Мур III
1
@ShelbyMooreIII Нет. Вы неправильно поняли концепцию недетерминизма, которая появляется в информатике.
Дэвид Ричерби
@DavidRicherby прости Дэвида. Перейдите в другую ветку и увидите, что я вас решительно опроверг. Вы можете попытаться опровергнуть логику, которую я изложил там. Простое утверждение без доказательств и объяснений не принесет вам никакой правды.
Шелби Мур III
18

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

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

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

Аарон Рот
источник
Относится к «волшебному выбору правильного элемента»: когда слово «недетерминизм» используется в этом смысле, люди иногда определяют его как «ангельский». Есть также «демонический» недетерминизм. (Тем не менее, как вы говорите, суть в том, что все происходит параллельно.)
Раду ГРИГОР
13

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

  • детерминированный означает «я могу выбирать»

  • недетерминированный означает «кто-то другой может выбирать»

  • случайный означает «никто не может выбирать»

Несколько примеров:

  1. [одновременный, случайный] Рассмотрим сетевой протокол, такой как Ethernet , где несколько узлов могут отправлять сообщения в любое время. Если два узла отправляют сообщение с очень близкими интервалами, возникает коллизия: сообщения перекрываются и не читаются. Если происходит коллизия, оба узла должны попытаться отправить сообщения снова позже. Представьте, что вы пишете спецификацию Ethernet. Как указать задержку между попытками? (Задержки должны быть другими, иначе снова будет столкновение!)

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

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

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

  2. [параллелизм, недетерминированный] Вы пишете параллельный алгоритм. В конкретной ситуации может возникнуть тупик. Как вы можете предотвратить возникновение тупика? Это зависит от того, какое планирование имеет ваша среда параллелизма.

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

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

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

  3. [security, random] Вы пишете приложение с запросом пароля. Как вы моделируете злоумышленника?

    • детерминированный: злоумышленник всегда использует одни и те же пароли. Это не полезная модель атакующего - атакующие не предсказуемы по определению.

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

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

  4. [безопасность, недетерминированная] Вы пишете приложение и беспокоитесь о том, что оно может иметь дыру в безопасности. Как вы моделируете злоумышленника?

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

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

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

Жиль "ТАК - прекрати быть злым"
источник
Исправление вращается вокруг пропущенного слова « доказать» в ваших утверждениях: «Детерминист» - это «Я могу доказать, что я выбираю (то есть полностью указать результат, который заканчивается на моем входе в класс сложности P)», Недетерминированный - «Я не могу доказать, что я выбираю (то есть доказательство завершения неразрешимо в классе сложности NP) », и случайным образом является« Я могу доказать, что я могу выбрать половину времени (то есть класс сложности ZPP) ».
Шелби Мур III
@ShelbyMooreIII Я не понимаю, куда ты клонишь. Детерминизм, как правило, не о том, чтобы доказать, что что-то действительно детерминировано, или о том, что какая-то проблема находится в определенном классе сложности. Кроме того, классы сложности не связаны с тем, что сама система способна что-то доказать в ее детерминизме (большинство проблем даже не имеют понятия о том, чтобы доказывать внутри системы!).
Жиль "ТАК - перестань быть злым"
Недетерминизм всегда является результатом неограниченной энтропии, поэтому другой способ сказать, что я не могу доказать, что я выбираю результат (потому что я не могу доказать, что мой выбор закончится). Все, что я могу сделать, это попробовать, а это значит, что я должен перечислить каждый выбор, который я хочу сделать, прежде чем я узнаю, что он закончится. Принимая во внимание, что с детерминизмом я могу доказать, что я выбираю результат, который он должен прекратить. Рандомизация - это то, где я могу доказать, что могу выбирать случайное количество времени, потому что некоторая энтропия не находится под моим контролем. Если я знаю сумму, которая не находится под моим контролем, я могу доказать точную статистику.
Шелби Мур III
Согласитесь, что не NP класса сложности порождает недетерминизм, а NP является зависимостью. Полная Тьюринг является примером недетерминизма. Пожалуйста, смотрите мой комментарий под ответом Курта, а также мой ответ в соответствующей теме . Я хочу сказать о том, что именно доказано и непредсказуемо для терминов детерминированный, недетерминированный и случайный. Это все об энтропии (а не о басе )
Шелби Мур III
9

Пример, чтобы прояснить ситуацию:

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

Робин Котари
источник
8
С другой стороны, недетерминированная машина открыла бы только одну дверь, но она всегда была бы правильной.
Джеффс
3
Да, точно. Это была бы самая «удачная из возможных догадок» характеристика недетерминированных машин.
Робин Котари
@RobinKothari: «Альтернативно, недетерминированная машина будет открывать только одну дверь, но она всегда будет правильной». И «Недетерминированная машина будет вводить все 10000 дверей одновременно»? - Какая из них верна?
tanmoy
3
@tan: оба являются правильными интерпретациями. В отличие от детерминированных и рандомизированных машин, которые физически реализуемы, недетерминированная машина является воображаемым объектом. Таким образом, вы можете себе это представить, как вам нравится, суть в том, что он всегда находит правильную дверь. Может быть, это лучший догадчик, может быть, кто-то тайно рассказал машине, где приз, может быть, он просто волшебным образом проверяет все двери и т. Д.
Робин Котари
5

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

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

Вероятностная машина Тьюринга - это недетерминированная машина Тьюринга, которая может совершать ошибки.

PPT я нашел полезным.

Пратик Деогхаре
источник
5

Я предпочитаю следующее определение:

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

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

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

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

MRA
источник
-1 Ошибки в вашем первом абзаце. Существуют вероятностные машины Тьюринга, которые отбрасывают монеты по внешней энтропии, например, по классу сложности ZPP. Недетерминизм имеет неограниченное, не конечное число альтернативных состояний, например, класс сложности NP. Детерминизм - это класс сложности P, и вы все правильно поняли.
Шелби Мур III
Я думаю, что вы не поняли мой ответ. Я утверждаю, что вам не нужна какая-либо другая машина (с подбрасыванием монет или другими возможностями), чем «обычная» недетерминированная ТМ для определения вероятностных классов сложности. С тем же успехом вы можете использовать NTM и просто использовать другое определение принятия, а именно определение, где «большинство вычислительных путей принимают входные данные», в отличие от «существует хотя бы один принимающий путь для входных данных».
MRA
3

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

Серж Гасперс
источник
1

Шаг назад во время отладки как мотив для недетерминизма

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

Сходства и различия между недетерминизмом и случайностью

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

  • Q
  • Σ
  • δ:Q×ΣQ
  • Δ:Q×ΣP(Q)
  • ΔQ×Σ×Q
  • Δ:ΣP(Q×Q)
  • δ:ΣssM(Q)

P(Q)QssM(Q)Q

Есть много разных приемлемых условий приемки

Переходы являются только одной частью машины, также важны начальное и конечное состояния, возможные условия вывода и приемки. Тем не менее, существует очень мало неэквивалентных условий приемки для детерминированных машин, ряд разумных условий приемки для недетерминированных машин (NP, coNP, #P, ...) и множество возможных условий приемки для вероятностных машин. Следовательно, этот ответ фокусируется в первую очередь на переходах.

Обратимость нетривиальна для вероятностных машин

PPTPPPBAkABk

Обратимость сложна даже для недетерминированных машин

PPTPPRRopRRRRRRopR=RRopRRop=RopPQPQ

Эти соображения также имеют смысл для автоматов

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

  • Q
  • Σ
  • Γ
  • δ:Q×Γ×(Σ{ϵ})Q×Γ{0,2}δ(q,γ,ϵ)ϵδ(q,γ,σ)=ϵσΣ
  • Δ:Q×Γ{0,1}×(Σ{ϵ})P(Q×Γ{0,1})
  • ΔQ×Γ{0,1}×(Σ{ϵ})×Q×Γ{0,1}
  • Δ:Σ{ϵ}P(Q×Γ{0,1} × Q×Γ{0,1})
  • δ:Σ{ϵ}ssM(Q×Γ{0,1})δ(ϵ)+δ(σ)ssM(Q×Γ{0,1})σΣ

ϵΓ{0,2}={ϵ}Γ(Γ×Γ)Γ{0,1}={ϵ}ΓΓ

Диаграмманная проверка реверса для (не) опережающих операций ввода и стека

bΣΣ{ϵ}

a|bca|bcab|c
a|bcab|cab|c
c|bac|bacb|a

ϵΣ{ϵ}

a|bca|bca|bc
a|bca|bca|bc
cb|acb|acb|a

Вот схема опережающей операции ввода, обращение которой будет выглядеть плохо

a|bca|bcab|ca|bcab|cab|cc|bac|bacb|a

Для операции стека существует три случая , и . Операция стека изменяется на следующим образом(s,t)Γ{0,1}×Γ{0,1}(s,t)=(a,ϵ)(s,t)=(ϵ,a)(s,t)=(a,b)(a,ϵ)(ϵ,a)

abab|b
ab|bb
b|bab

Операция стека обращается к следующим образом(a,b)(b,a)

acacbc
acbcbc
bcbcac

Обобщенная операция стека будет обращена к(ab,cde)Γ×Γ(cde,ab)

abfabfcdef
abfcdefcdef
cdefcdefabf

Обратимость для машин Тьюринга

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

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

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

Вывод

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

Томас Климпел
источник
Вы предполагаете, что недетерминированные переходы являются отношениями один-ко-многим? Что, если две разные конфигурации могут перейти к общей конфигурации, среди других? - Мне кажется, что разница между случайностью и недетерминизмом заключается не в обратимости (как и без дополнительных ограничений), а в том, как можно приписать значимость ветвям в зависимости от результата: совершенно демократично для случайности или преимущественно чувствительно к «да» или «нет» отвечает за недетерминизм.
Ниль де Бодрап,
@NieldeBeaudrap Я предполагаю, что недетерминированные переходы являются «произвольными» отношениями (по одному на каждый символ входного алфавита). Я могу поменять их местами, поменять местами начальное и конечное состояние и снова получить недетерминированный конечный автомат, который принимает обратную входную строку. Это то, что я называю «запустить машину назад во времени». (Машина принимает, если в недетерминированном случае есть хотя бы один путь от начального до конечного состояния, и это условие не изменяется при изменении времени.) Пожалуйста, попытайтесь убедить себя, что это работает, по крайней мере, для конечного автомата ,
Томас Климпел
Итак, вы ссылаетесь на дуал машины. Для НФА это кажется значимым понятием обратимости. Также очевидно, что дуал NTM (с единственным состоянием принятия) - это еще один NTM, но я бы не решился сказать, что это та же самая машина, которая работает в обратном направлении. Означает ли ваш ответ только «Недетерминизм позволяет вам получить замыкание по двойственным, случайным (и детерминированным) машинам нет»?
Ниль де Бёдрап
@NieldeBeaudrap Моя идея, конечно, состоит в том, чтобы двигаться назад во времени, но я знаю, что это не выполняется полностью (потому что условия для обобщенного обращения обратной полугруппы не выполняются). Но то, что я пытался донести, это то, что случайные (и детерминированные) машины не всегда допускают такого рода разворот.
Томас Климпел
0

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

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

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

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

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

Никос М.
источник