Qual é a diferença entre não determinismo e aleatoriedade?

38

Eu ouvi recentemente isso:
"Uma máquina não determinística não é a mesma que uma máquina probabilística. Em termos brutos, uma máquina não determinística é uma máquina probabilística na qual as probabilidades de transições não são conhecidas".

Sinto como se entendi, mas realmente não entendo. Alguém poderia me explicar isso (no contexto de máquinas ou em geral)?

Edit 1:
Apenas para esclarecer, a citação estava no contexto de autômato finito, mas a pergunta também é significativa para as máquinas de Turing, como outras pessoas responderam.

Além disso, ouço as pessoas dizerem "... então escolho o objeto x do conjunto de maneira não determinística". Eu achava que eles queriam dizer "aleatoriamente". Daí a confusão.


fonte
5
Na ciência da computação, as pessoas ocasionalmente usam o termo "determinístico" para enfatizar que um algoritmo não é randomizado. Daí a confusão: determinístico significa não randomizado, mas não determinístico não significa randomizado.
Jukka Suomela 26/08/10
Esta questão leva-me a este canto de SE ...
Troy Woo

Respostas:

27

É importante entender que os cientistas da computação usam o termo "não-determinístico" de maneira diferente de como é normalmente usado em outras ciências. Uma MT não determinística é realmente determinística no sentido da física - ou seja, um MNT sempre produz a mesma resposta em uma determinada entrada: ele sempre aceita ou sempre rejeita. Uma TM probabilística aceitará ou rejeitará uma entrada com uma certa probabilidade; portanto, em uma execução, ela pode aceitar e em outra pode rejeitar.

Mais detalhadamente: em cada etapa da computação realizada por um NTM, em vez de ter uma única regra de transição, existem várias regras que podem ser invocadas. Para determinar se o NTM aceita ou rejeita, verifique todas as ramificações possíveis da computação. (Portanto, se houver, digamos, exatamente 2 transições para escolher em cada etapa e cada ramo de computação tiver um total de N etapas, haverá totais de ramificações a serem consideradas.) Para um NTM padrão, uma entrada é aceita se algum dos ramos da computação aceitar.2N

Esta última parte da definição pode ser modificada para obter outros tipos relacionados de máquinas de Turing. Se você estiver interessado em problemas com uma solução exclusiva, poderá aceitar a TM se exatamente uma filial aceitar. Se você estiver interessado no comportamento majoritário, poderá definir a TM para aceitar se mais da metade das filiais aceitarem. E se você escolher aleatoriamente (de acordo com alguma distribuição de probabilidade) um dos possíveis ramos e aceitar ou rejeitar com base no que esse ramo faz, então você tem uma TM probabilística.

Kurt
fonte
Kurt, você pode explicar como chegou a figura 2 ^ N. Se para cada ramo existem 2 possibilidades e há N estágios para alcançar a solução, isso não seria 2 ^ (N + 1) -1. Estou tentando pensar nisso como um gráfico e posso estar errado. Você poderia explicar como chegou ao número 2 ^ N. Obrigado.
Gangadhar
Bem, se você representa o cálculo como uma árvore, com a raiz representando a configuração inicial como etapa 0, depois de N etapas você tem 2 ^ N folhas, e o que estou chamando de ramificação é um caminho da raiz para uma folha. É verdade que você terá 2 ^ (N + 1) -1 nós no total, representando todas as configurações possíveis em algum momento da computação. Espero que minha terminologia esteja bem!
Kurt
Todas as ciências usam a mesma definição de não determinismo unificada no conceito de entropia ilimitada. Resultados imprevisíveis em todas as ciências devem-se à incapacidade de enumerar a priori todas as saídas possíveis de um algoritmo (ou sistema) porque ele aceita estados ilimitados, ou seja, classe de complexidade NP. Especificar uma entrada específica para observar se ela para e notar que o resultado é idempotente é equivalente em outras ciências a manter o resto da entropia do universo constante enquanto repete a mesma mudança de estado. A computação permite esse isolamento de entropia, enquanto as ciências naturais não.
Shelby Moore III
1
@ShelbyMooreIII Não. Você entendeu mal o conceito de não determinismo que aparece na ciência da computação.
David Richerby
@DavidRicherby desculpe David. Vá para o outro tópico e veja que eu refutei você de maneira retumbante. Você pode tentar refutar a lógica que apresentei lá. Apenas afirmar sem evidência e explicação não ganha nenhuma verdade.
Shelby Moore III
18

No contexto das máquinas de Turing, "não determinístico" realmente significa "paralelo". Um algoritmo aleatório pode explorar aleatoriamente os ramos da árvore de computação de uma máquina de Turing não determinística, mas uma máquina de Turing não determinística pode explorá-los - todos - ao mesmo tempo, e é isso que lhe dá seu poder.

Em outros contextos (não posso dizer da sua citação se você está falando sobre Máquinas de Turing), um algoritmo aleatório pode estar intencionalmente usando aleatoriedade, enquanto um algoritmo que você queria ser determinístico pode acabar exibindo não-determinismo por causa de um bug ...

Em resposta à sua edição, quando as pessoas dizem "escolher um elemento de um conjunto de forma não determinística", é possível que elas signifiquem apenas "aleatoriamente". No entanto, também é possível que eles signifiquem "escolha magicamente o elemento certo do conjunto". Uma maneira comum de visualizar máquinas de turing não determinísticas é que elas primeiro “adivinham” magicamente uma solução e depois verificam sua correção. Obviamente, você pode ver esse palpite mágico como apenas o resultado de verificar todas as possibilidades em paralelo.

Aaron Roth
fonte
Relacionado a "escolher magicamente o elemento certo ": Quando a palavra 'não determinismo' é usada nesse sentido, as pessoas às vezes a qualificam como 'angelical'. Há também um não determinismo "demoníaco". (Ainda assim, como você diz, a essência é que as coisas acontecem em paralelo.)
Radu Grigore
13

Existem vários contextos diferentes em que "determinístico", "aleatório" e "não determinístico" significam três coisas diferentes. Em contextos em que há vários participantes, como segurança e simultaneidade, a intuição geralmente é algo como:

  • determinístico significa "eu escolho"

  • não determinístico significa "alguém escolhe"

  • random significa "ninguém escolhe"

Alguns exemplos:

  1. [simultaneidade, aleatória] Considere um protocolo de rede como Ethernet , em que vários nós podem enviar uma mensagem a qualquer momento. Se dois nós enviam uma mensagem em intervalos muito próximos, há uma colisão: as mensagens se sobrepõem e são ilegíveis. Se ocorrer uma colisão, os dois nós devem tentar enviar as mensagens novamente mais tarde. Imagine que você está escrevendo a especificação da Ethernet. Como você especifica o atraso entre novas tentativas? (É melhor que os atrasos sejam diferentes ou haverá uma colisão novamente!)

    • determinístico: define um algoritmo que os dois nós devem usar. Isso não é feito para a Ethernet porque, para fornecer resultados diferentes, o algoritmo precisaria privilegiar um nó sobre o outro (para qualquer conteúdo de mensagem), e a Ethernet evita isso.

    • não determinístico: permita que cada implementador decida. Isso não é bom porque os implementadores nos dois nós podem escolher o mesmo algoritmo.

    • random: cada nó deve selecionar um valor de atraso aleatoriamente (com uma distribuição especificada). É assim que funciona. Há uma pequena probabilidade de os dois nós escolherem o mesmo atraso e há outra colisão, mas a probabilidade de sucesso aumenta assintoticamente em direção a 1 à medida que o número de tentativas aumenta.

  2. [simultaneidade, não determinística] Você escreve um algoritmo simultâneo. Em uma situação específica, pode haver um impasse. Como você pode impedir que o impasse ocorra? Isso depende de que tipo de agendamento seu ambiente de simultaneidade possui.

    • determinístico: o planejador sempre alterna entre threads em determinados pontos bem definidos, por exemplo, apenas quando o código é explicitamente produzido. Então você simplesmente organiza para que os encadeamentos não cedam em momentos ruins.

    • random: é garantido que o planejador alterne os threads aleatoriamente. Uma estratégia viável pode ser detectar o impasse, se ocorrer, e reiniciar o algoritmo desde o início.

    • não determinístico (a maioria dos agendadores é assim): você não sabe quando o agendador alternará entre threads. Então você realmente tem que evitar o impasse. Se você tentou detectar e reiniciar como no caso aleatório, corre o risco de o agendador agendar seus encadeamentos exatamente da mesma maneira repetidamente.

  3. [segurança, aleatória] Você escreve um aplicativo com um prompt de senha. Como você modela um invasor?

    • determinístico: o invasor sempre tenta as mesmas senhas. Esse não é um modelo útil de um invasor - os invasores não são previsíveis por definição.

    • não determinístico: o invasor conhece sua senha de alguma forma e a insere. Isso mostra a limitação das senhas: elas devem ser mantidas em segredo. Se sua senha é secreta, esse invasor não é realista.

    • random: o invasor tenta senhas aleatoriamente. Nesse caso, este é um modelo realista de invasor. Você pode estudar quanto tempo levaria para o invasor adivinhar sua senha, dependendo da distribuição aleatória que ele usa. Uma boa senha é aquela que demora muito para qualquer distribuição realista.

  4. [segurança, não determinística] Você escreve um aplicativo e se preocupa que ele possa ter uma falha de segurança. Como você modela um invasor?

    • determinista: o atacante sabe tudo o que sabe. Novamente, esse não é um modelo útil de invasor.

    • random: o atacante joga lixo aleatório e espera que seu programa falhe. Às vezes, isso pode ser útil ( confuso ), mas o invasor pode ser mais inteligente do que isso.

    • não determinístico: se houver um buraco, o atacante o encontrará eventualmente. Portanto, é melhor você fortalecer sua aplicação (aumentar o requisito de inteligência para o invasor; observe que, como é um requisito de inteligência e não um requisito de computação, isso conta como não determinístico até que a IA apareça), ou melhor, prove que não há falha de segurança e, portanto, esse invasor não existe.

Gilles 'SO- parar de ser mau'
fonte
Correção gira em torno da palavra que falta provar em suas declarações: Determinístico é "Eu posso provar que estou escolhendo (ou seja, especificando totalmente o resultado que termina com minha entrada na classe de complexidade P)", Não determinístico é "Não posso provar que estou escolhendo (ou seja, a prova de término é indecidível na classe de complexidade NP) ”e aleatória é“ Eu posso provar que posso escolher metade do tempo (ou seja, classe de complexidade ZPP) ”.
Shelby Moore III
@ShelbyMooreIII Não entendo de onde você está chegando. O determinismo não é, em geral, sobre provar que algo é realmente determinístico, ou sobre algum problema em uma determinada classe de complexidade. Além disso, as classes de complexidade não são sobre o próprio sistema ser capaz de provar algo sobre seu determinismo (a maioria dos problemas nem sequer tem noção de provar dentro do sistema!).
Gilles 'SO- stop be evil' -
O não determinismo é sempre o resultado da entropia ilimitada, portanto, outra maneira de dizer isso é que não posso provar que estou escolhendo o resultado (porque não posso provar que minha escolha será encerrada). Tudo o que posso fazer é tentar, o que significa que devo enumerar todas as opções que quero fazer antes de saber se será encerrado. Considerando que, com o determinismo, posso provar que escolho o resultado que deve terminar. A randomização é onde eu posso provar que só consigo escolher uma quantidade aleatória de tempo, porque parte da entropia não está sob meu controle. Se eu souber o valor que não está sob meu controle, posso provar com precisão as estatísticas de.
Shelby Moore III
Concordou que não é a classe de complexidade NP que dá origem ao não-determinismo, mas NP é uma dependência. Turing-complete é um exemplo de não-determinismo. Por favor, veja meu comentário na resposta de Kurt, bem como minha resposta no tópico relacionado . Meu argumento para você é sobre o que é precisamente provado e imprevisível para os termos determinístico, não determinístico e aleatório. É tudo sobre a entropia (e não sobre o baixo )
Shelby Moore III
9

Um exemplo para tornar as coisas mais claras:

Digamos que você precise escolher uma porta para abrir entre 10.000 portas (digamos que haja um prêmio atrás de uma das portas). Escolher aleatoriamente significa que você escolheria uma das 10000 portas e a entraria. Se houver um prêmio atrás de apenas uma porta, você provavelmente não o encontrará. Uma máquina não determinística entraria em todas as 10000 portas simultaneamente. Se houver um prêmio em qualquer lugar, a máquina não determinística o encontrará.

Robin Kothari
fonte
8
Como alternativa, uma máquina não determinística abriria apenas uma porta, mas seria sempre a correta.
precisa saber é o seguinte
3
Sim, exatamente. Essa seria a caracterização "mais acertado possível" de máquinas não determinísticas.
Robin Kothari
@RobinKothari: "Alternativamente, uma máquina não determinística abriria apenas uma porta, mas sempre seria a certa". E "Uma máquina não determinística entraria em todas as 10000 portas simultaneamente"? - Qual é a correta?
Tanmoy
3
@tan: Ambos são interpretações corretas. Diferentemente das máquinas determinísticas e aleatórias, que são fisicamente realizáveis, uma máquina não determinística é um objeto imaginário. Para que você possa imaginá-lo como quiser, o ponto é que ele sempre encontra a porta certa. Talvez seja o melhor adivinhador, talvez alguém secretamente disse a máquina onde o prêmio era, talvez ele apenas verifica todas as portas magicamente, etc.
Robin Kothari
5

Definição de máquina de Turing não determinística : Uma máquina de Turing que possui mais de um próximo estado para algumas combinações de conteúdo da célula atual e do estado atual. Uma entrada é aceita se qualquer sequência de movimentação levar à aceitação.

Definição de Máquina de Turing Probabilitística : Uma Máquina de Turing não determinística (TM) que escolhe aleatoriamente entre as transições disponíveis em cada ponto, de acordo com alguma distribuição de probabilidade.

A máquina de Turing probabilística é uma máquina de Turing não determinística que pode cometer erros.

PPT eu achei útil.

Pratik Deoghare
fonte
5

Eu prefiro a seguinte definição:

Não existe uma máquina de Turing probabilística! Existem apenas máquinas determinísticas (em todas as etapas um único estado de acompanhamento possível) e máquinas não determinísticas (em todas as etapas um número constante de possíveis estados de acompanhamento).

O não determinismo funciona da seguinte maneira: considere uma máquina não determinística que para em cada entrada (possível se o problema for decidido), em que cada cálculo possível usa o mesmo número de etapas e em que cada etapa possui exatamente 2 estados possíveis de acompanhamento ( ambos não são realmente uma restrição). Como na definição de NP, uma máquina não determinística aceita uma entrada se houver pelo menos uma computação possível de aceitação e rejeita a entrada se todas as computações rejeitarem.

A aleatoriedade entra em jogo da seguinte maneira: Você pode escolher uniformemente aleatoriamente um único caminho de computação a partir de uma máquina não determinística, como indicado acima. Você aceita se e somente se esse caminho de cálculo escolhido aleatoriamente aceitar. Essa abordagem aleatória "resolve" o seu problema se, com uma probabilidade esmagadora, essa resposta estiver correta.

Portanto, a diferença entre não-determinismo e aleatoriedade é se você está procurando a mera existência de uma resposta correta do Sim (e não-confiável) ou se está interessado em resolver o seu problema "na maioria das vezes" .

MRA
fonte
-1 Erros no seu primeiro parágrafo. Existem máquinas probabilísticas de Turing e amostram um sorteio da entropia externa, conforme a classe de complexidade ZPP. O não determinismo tem um número ilimitado e ilimitado de estados alternativos, conforme a classe de complexidade NP. O determinismo é a classe de complexidade P e você acertou.
Shelby Moore III
Eu acho que você está interpretando mal a minha resposta. Argumento que você não precisa de nenhuma máquina diferente (com lançamento de moeda ou outros recursos) do que uma MT não determinística "comum" para definir classes de complexidade probabilística. Você também pode usar um NTM e apenas usar uma definição diferente de aceitação, ou seja, uma definição em que "a maioria dos caminhos computacionais aceita a entrada", em oposição a "existe pelo menos um único caminho de aceitação para a entrada".
MRA
3

Para simplificar: uma máquina não determinística pode escolher da melhor maneira o resultado de cada troca de moeda (se você gosta da analogia com uma máquina probabilística). Você também pode imaginar que ele executa o cálculo para cada resultado do lançamento da moeda em paralelo.

Serge Gaspers
fonte
1

Recuando durante a depuração como motivação para o não determinismo

A noção de uma máquina não determinística se sugere quando você deseja retroceder (no tempo) através de um programa durante a depuração. Em um computador típico, cada etapa modifica apenas uma quantidade finita de memória. Se você sempre salvar essas informações nas 10000 etapas anteriores, poderá avançar e retroceder muito bem no programa, e essa possibilidade não se limita aos programas de brinquedo. Se você tentar remover a assimetria entre as etapas para frente e para trás, você terá a noção de uma máquina não determinística.

Semelhanças e diferenças entre não determinismo e aleatoriedade

Enquanto as máquinas probabilísticas compartilham algumas características com as máquinas não determinísticas, essa simetria entre as etapas anteriores e posteriores não é compartilhada. Para ver isso, vamos modelar as etapas ou transições de uma máquina determinística por funções (totais ou parciais), as transições de uma máquina não determinística por relações (finitas) e as transições de uma máquina probabilística por matrizes (sub) estocásticas . Por exemplo, aqui estão as definições correspondentes para autômatos finitos

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

P(Q)QssM(Q)Q

Existem muitas condições razoáveis ​​de aceitação diferentes

As transições são apenas uma parte da máquina, estados inicial e final, possíveis condições de saída e aceitação também são importantes. No entanto, existem muito poucas condições de aceitação não equivalentes para máquinas determinísticas, várias condições razoáveis ​​de aceitação para máquinas não determinísticas (NP, coNP, #P, ...) e muitas condições possíveis de aceitação para máquinas probabilísticas. Portanto, esta resposta se concentra principalmente nas transições.

A reversibilidade não é trivial para máquinas probabilísticas

PPTPPPBAkABk

A reversibilidade é complicada mesmo para máquinas não determinísticas

PPTPPRRopRRRRRRopR=RRopRRop=RopPQPQ

Essas considerações também fazem sentido para os autômatos de empilhamento

Este post sugere que uma motivação para o não-determinismo é remover essa assimetria entre as etapas anteriores e posteriores. Essa simetria do não-determinismo é limitada a autômatos finitos? Aqui estão as definições simétricas correspondentes para autômatos de empilhamento

  • 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}={ϵ}ΓΓ

Verificação diagramada de reversão para operações de entrada e pilha (sem avanço)

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

Aqui está um diagrama de uma operação de entrada avançada cuja reversão ficaria ruim

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

Reversibilidade para máquinas de Turing

Uma máquina com mais de uma pilha é equivalente a uma máquina de Turing, e as operações da pilha podem ser facilmente revertidas. A motivação no início também sugere que a reversão (de uma máquina de Turing) não deve ser difícil. Uma máquina de Turing com um conjunto de instruções típico não é tão boa para reversão, porque o símbolo sob a cabeça pode influenciar se a fita se moverá para a esquerda ou direita. Mas se o conjunto de instruções for modificado adequadamente (sem reduzir o poder computacional da máquina), a reversão será quase trivial novamente.

Uma reversão também pode ser construída sem modificar o conjunto de instruções, mas não é canônica e um pouco feia. Pode parecer que a existência de uma reversão é tão difícil de decidir quanto muitas outras questões referentes às máquinas de Turing, mas uma reversão é uma construção local e as perguntas difíceis geralmente têm um sabor global; portanto, o pessimismo provavelmente seria injustificado aqui.

O desejo de mudar para conjuntos de instruções equivalentes (mais fáceis de reverter) mostra que essas perguntas são menos óbvias do que parecem à primeira vista. Uma mudança mais sutil aconteceu neste post antes, quando as funções totais e matrizes estocásticas foram substituídas por funções parciais e matrizes sub-fasásticas. Essa opção não é estritamente necessária, mas a reversão é feia caso contrário. A mudança para as matrizes subsocásticas foi na verdade o ponto em que ficou óbvio que a reversibilidade não é tão trivial, afinal, e que se deve anotar detalhes (como feito acima) em vez de assumir apenas uma perspectiva de alto nível (como apresentado na motivação em o início). As questões levantadas por Niel de Beaudrap também contribuíram para a percepção de que a perspectiva de alto nível é um pouco instável.

Conclusão

Máquinas não determinísticas permitem um número finito de transições determinísticas em cada etapa. Para máquinas probabilísticas, essas transições têm adicionalmente uma probabilidade. Este post traz uma perspectiva diferente sobre o não determinismo e a aleatoriedade. Ignorando as condições globais de aceitação, ele se concentra na reversibilidade local (como uma simetria local). Como a aleatoriedade preserva algumas simetrias locais que não são preservadas pelo determinismo, essa perspectiva revela diferenças não triviais entre máquinas não determinísticas e probabilísticas.

Thomas Klimpel
fonte
Você está assumindo que as transições não determinísticas são relações um para muitos? E se duas configurações diferentes puderem fazer a transição para uma configuração comum, entre outras? - Parece-me que a diferença entre aleatoriedade e não-determinismo não é reversibilidade (nem são, sem maiores restrições), mas sim como se atribui significado a ramificações de acordo com o resultado: perfeitamente democrático para a aleatoriedade ou preferencialmente sensível ao "sim" ou respostas "não" para não-determinismo.
Niel de Beaudrap
@NieldeBeaudrap Presumo que as transições não determinísticas sejam relações "arbitrárias" (uma para cada símbolo do alfabeto de entrada). Posso revertê-los, trocar os estados inicial e final e obter novamente uma máquina de estados finitos não determinística, que aceita a sequência de entrada invertida. Isso é o que eu chamo de "executar a máquina para trás no tempo". (A máquina aceita se existe pelo menos um caminho do estado inicial ao final no caso não determinístico, e essa condição não muda ao reverter o tempo.) Tente convencer-se de que isso funciona pelo menos para uma máquina de estados finitos .
Thomas Klimpel
Então, você se refere ao dual da máquina. Para as AFN isso parece uma noção significativa de reversibilidade. Também está claro que o dual de um NTM (com um único estado de aceitação) é outro NTM, mas eu hesitaria em dizer que é a mesma máquina sendo executada ao contrário. Sua resposta equivale apenas a "O não determinismo permite que você obtenha fechamento sob duals, máquinas aleatórias (e determinísticas) não são"?
Niel de Beaudrap
@NieldeBeaudrap Minha idéia é certamente retroceder no tempo, mas sei que isso não é satisfeito perfeitamente (porque as condições para uma inversa generalizada de um semigrupo inverso não são satisfeitas). Mas o que tentei transmitir é que máquinas aleatórias (e determinísticas) nem sempre permitem esse tipo de reversão.
Thomas Klimpel
Escrevi esta resposta em um post de blog sobre Reversibilidade de relações binárias, matrizes sub-fasásticas e funções parciais .
Thomas Klimpel
0

n2n exponencial) considerando classes de equivalência de estados, não importa se o algoritmo implementado na máquina envolve randomização ou probabilidades (veja abaixo).

Mas se o algoritmo implementado na máquina envolve randomização ou probabilidades (intrínsecas ao algoritmo), então é uma máquina randomizada (ou probabilística).

Em geral, sempre é possível remover o não-determinismo de uma máquina e construir um equivalente determinístico (veja o algoritmo acima), mas o mesmo não pode ser feito (em geral) para remover a randomização (no contexto do acima), porque é intrínseco ao algoritmo implementado .

Observe que, à luz do exposto, tanto uma máquina determinística quanto uma máquina não determinística podem ser probabilísticas se o algoritmo (envolvido) usar randomização (ou probabilidades) dessa maneira.

Em resumo, o não determinismo nos autômatos (neste contexto) refere-se a classes de autômatos semelhantes, enquanto as máquinas de randomização ou probabilística se referem aos (aplicação intrínseca da randomização nos) algoritmos reais implementados por esses autômatos.

Nikos M.
fonte