Por que o não-determinismo é um conceito útil?

23

Um autômato é um modelo abstrato de um computador digital. Computadores digitais são completamente determinísticos; seu estado a qualquer momento é previsível exclusivamente a partir da entrada e do estado inicial.

Quando estamos tentando modelar sistemas reais, por que incluir o não determinismo na teoria de Autômatos?

tanmoy
fonte
1
Possivelmente ajudaria a perguntar quem descreveu originalmente as MNTs e qual era o seu objetivo / objetivo na época.
usul
2
Observe que o fato de a máquina ser determinística nem sempre significa que nosso código é. Qualquer pessoa que tenha feito multitarefa / multithreading pode atestar o fato de que os horários nos quais a alternância de tarefas ocorre são muitas vezes imprevisíveis em termos práticos e temos que projetar intertravamentos explícitos para fazer com que seu comportamento pareça determinístico. (Basicamente, existem variáveis ​​ocultas no estado.) A comunicação levanta o mesmo problema. Sinceramente, não sei se os NDAs ajudam a resolver esses problemas - sou engenheiro de software, não cientista da computação - mas, no mundo real, sua premissa é otimista demais.
keshlam
Quando você fala sobre multithreading, pode-se argumentar que não possui determinismo, pelo menos se considerar o metal e o SO para formar a máquina. O engraçado é que o próprio código é determinístico.
Raphael
@ Raphael, @keshlam Em outras palavras, podemos dizer que "modelos não-determinística também são úteis para simular a execução paralela de código"
Grijesh Chauhan
@keshlam Adicionei seu ponto na minha resposta, @ Tanmoy leu atualizou minha resposta.
Grijesh Chauhan 13/03

Respostas:

16

Sim, você está correto, os computadores são determinísticos e automatizam. Modelos não determinísticos são mais úteis para fins teóricos, às vezes a solução determinística não é tão óbvia para a definição (ou seja, para a afirmação do problema) e tão pouco difícil de encontrar solução. Então, uma abordagem é que primeiro projete um modelo não determinístico que possa ser relativamente fácil de projetar e tente convertê-lo em um determinístico. Abaixo, tentei demonstrar o que quero dizer com um exemplo. Considere expressão regular:

(01)*01(0 + 1)*  

Agora, suponha que, se você for solicitado a desenhar o DFA para o idioma gerado pelo RE acima.

Com o meu conhecimento de projetar FAs, eu sei que (1) quando um *presente na expressão regular indicada eu preciso circuito correspondente na FA (2) operações concatenar como a.bsignifica algo como: .(q0)─a→(q1)─b→(q2)

Então, na minha primeira tentativa, eu desenharia uma NFA como:

FIG

Achei que essa não é uma solução determinística, mas parece uma FA muito simples que pode ser facilmente projetada usando a expressão regular fornecida. Meu tipo de analogia para mostrar semelhança entre a expressão regular acima e meu NFA é como abaixo:

  1. O loop no estado q 0 deve ser para(01)*
  2. 01(depois (01)*) dá(q0)─0→(q1)─1→(q2)
  3. (0 + 1)* dá um auto loop no estado q 2 para o rótulo 0, 1

De acordo com minha analogia, acho que a AF que desenhei acima é comparativamente simples de extrair de um dado ER. E, felizmente, na classe dos autômatos finitos, todo modelo não determinístico pode ser convertido em um modelo determinístico equivalente. Temos um método algorítmico para converter um NFA em DFA . Para que eu possa converter facilmente acima do NFA em um DFA:

Figura 2

Outra parte é que infelizmente nem sempre é possível converter um modelo não determinístico em determinístico, por exemplo, classe para automação push-down determinística é um subconjunto da classe de automação push-down determinística "check venn diagram " e você nem sempre pode converter um NPDA em um PDA.

Normalmente, quando não é possível converter uma solução não determinística em uma determinística, com a ajuda de uma solução não determinística, definimos a solução determinística no subdomínio (ou seja, domínio parcial) em vez do domínio completo. Ou então definimos a solução de outras maneiras (por exemplo, abordagem gananciosa) que, é claro, podem não fornecer uma solução ideal .

Às vezes, o não determinismo é um mecanismo eficaz para descrever com precisão e eficácia algum problema / solução complicada, por exemplo, máquinas não determinísticas podem servir como modelo de algoritmo de busca e retorno (leia-se: Como processo de cadeia de caracteres no modelo não determinístico usando retorno ) Modelos deterministicamente opostos representam melhor soluções eficientes, minimizadas e menos redundantes.

Aqui também gostaria de citar o uso da Wikipedia de algoritmo não determinístico :

No design de algoritmos, algoritmos não determinísticos são freqüentemente usados ​​quando o problema resolvido pelo algoritmo permite inerentemente vários resultados (ou quando há um único resultado com vários caminhos pelos quais o resultado pode ser descoberto, cada um igualmente preferível). Fundamentalmente, todos os resultados que o algoritmo não determinístico produz são válidos, independentemente de quais escolhas o algoritmo faz durante a execução.

Um grande número de problemas pode ser conceituado através de algoritmos não determinísticos, incluindo a questão não resolvida mais famosa da teoria da computação, P vs NP.

Como @keshlam também mencionou em seu comentário : "Não determinismo" é na prática usado para se referir a qualquer imprevisibilidade no resultado de algum processo. Por exemplo, programas concorrentes exibem comportamento não determinístico - duas execuções do mesmo programa com a mesma entrada podem produzir resultados diferentes (se o mecanismo de controle de simultaneidade não for aplicado). Leia mais sobre isso em "Utilidade do não determinismo" .

Eu também sugiro que você leia os seguintes links:
1. Qual é a diferença entre não-determinismo e aleatoriedade?
2. 9.2.2 Modelos não determinísticos x probabilísticos: (a). Não determinístico: não tenho ideia do que a natureza fará. b) Probabilístico: tenho observado a natureza e colecionado estatísticas.
3. Programação não determinística

Grijesh Chauhan
fonte
@ Grijest: muito obrigado por uma elaboração tão grande. Apenas uma confusão: "Os modelos deterministas opostos representam melhor as soluções eficientes, minimizadas e menos redundantes." - Mas acho que os modelos determinísticos são menos eficientes do que os não determinísticos. (É por isso que os problemas de PN são mais complexas do P. não é)?
Tanmoy
@tan Na verdade, a palavra "eficiente" está errada. Sim, você está certo de que os modelos não determinísticos são mais capazes do que os determinísticos. A classe de problemas cobertos pelos modelos determinísticos é um subconjunto do modelo não determinístico.
Grijesh Chauhan 21/03
Então, em que contexto os modelos determinísticos são "eficientes" que os não-determinísticos (como você mencionou)?
Tanmoy
@tan Suponha que se você deseja realizar mais operações (por exemplo, converter FA em RE, ou explicar provas de bombeamento de lema ou algum outro ..), o modelo determinístico fornece melhores resultados (então eu disse eficiente).
Grijesh Chauhan 21/03
@tan Você entende gramáticas ambíguas?
Grijesh Chauhan 26/03
9

É mais o contrário: os autômatos surgiram primeiro, como modelos matemáticos. E o não-determinismo é bastante natural; muitas vezes você tem vários caminhos abertos diante de você. Em vez de uma maneira confusa de especificar que todos os caminhos devem ser seguidos até o fim em alguma ordem, e talvez ficar atolados por galhos infinitos, e ... use apenas o não-determinismo.

E embora as linguagens de programação não determinísticas não sejam comuns, elas têm uma história ilustre, talvez começando com a GCL de Dijkstra . À medida que as máquinas somam mais e mais núcleos (processadores independentes), alguma forma de não-determinismo está se infiltrando em toda a programação.

vonbrand
fonte
Acho que a primeira parte da sua resposta está realmente errada. Por que você acha que os autômatos surgiram primeiro? Os DFAs e os NFAs foram definidos 10 anos ou mais após as TMs definidas por Turing. Veja a discussão sobre cstheory
Artem Kaznatcheev
@ArtemKaznatcheev, o modelo de máquina de Turing é um autômato e certamente antecede os computadores há pelo menos uma década.
vonbrand
sim, mas quando as pessoas dizem autômatos, elas não significam MT, mas sim autômatos de estados finitos e suas extensões diretas (PDAs, NPDAs, etc.). Veja a pergunta que eu vinculei para uma história lá e você verá que as TMs e a arquitetura de von Neumann foram desenvolvidas independentemente do que chamamos agora de teoria dos autômatos.
Artem Kaznatcheev
4
@ArtemKaznatcheev, DFA / NFA, PDA, LBA, TM são todos autômatos. Assim como os transdutores (FA com saída, PDA com saída).
vonbrand
1
O último parágrafo está errado. O Prolog é anterior à GCL e ainda é bastante comum. O prólogo, é claro, não foi projetado no vácuo, baseado em linguagens de programação não determinísticas anteriores, como o PLANNER. O crédito provavelmente vai para Golomb e Baumert "Backtrack Programming" de 1965.
Pseudônimo
7

Os NFAs podem ser usados ​​na prática, confira esta resposta no stackexchange. O motivo é que a construção do conjunto de potências pode ser simulada on-the-fly, por assim dizer. Para simular um NFA em um computador determinístico, apenas acompanhamos os possíveis estados em que o NFA pode estar. Normalmente, esse número seria pequeno e, portanto, a simulação seria rápida. Isso é muito mais prático do que executar a construção real do conjunto de potências: o autômato resultante pode ser muito grande, embora na prática a maioria dos conjuntos raramente seja alcançada.

O não determinismo também é importante para a complexidade da computação, onde é usado para definir a classe NP. (A classe NP também possui outras definições equivalentes, por exemplo, usando testemunhas.)

Yuval Filmus
fonte
entendendo sua resposta, mas não consegui entendê-la adequadamente. Você poderia elaborar o fato de como a construção de conjuntos de potências pode ser feita facilmente usando o não-determinismo?
Tanmoy
"O não determinismo também é importante para a complexidade da computação, onde é usado para definir a classe NP." - que apóia a importância do não-determinismo apenas se assumirmos que NP é um conceito útil, o que é apenas se o não-determinismo for útil.
Raphael
@Raphael NP-completude é um conceito importante, independentemente da sua posição em relação ao não-determinismo.
Yuval Filmus
2
@ Tanmoy Se você não tem um determinismo, não precisa da construção do conjunto de potências, mas, infelizmente, os computadores reais são determinísticos. No entanto, pode ser mais fácil simular diretamente um NFA do que convertê-lo em um DFA primeiro. Confira a resposta que eu vinculo para obter mais detalhes.
Yuval Filmus
4

Você declara corretamente que os autômatos são modelos, portanto, existem duas partes de uso que o não-determinismo pode ter:

  1. Use na modelagem de problemas reais.

    Além disso, autômatos não determinísticos podem fornecer representações mais compactas de linguagens. Por exemplo, é sabido que existem NFA cujo DFA equivalente mínimo é exponencialmente maior.

  2. Use na teoria.

    O uso do não-determinismo pode simplificar as provas, veja, por exemplo, a conversão de expressões regulares em autômatos finitos.

Rafael
fonte
4

(Esta é uma reformulação de algumas das outras respostas, mas eu a postarei de qualquer maneira :)

Você escreve: Um autômato é um modelo abstrato de um computador digital.

Discordo! Os autômatos modelam como nós humanos especificamos a computação, não apenas como os computadores a executam. Não-determinismo é exatamente a diferença. Nossas especificações geralmente não são determinísticas.

Por exemplo, faça a classificação de mesclagem . A classificação de mesclagem é classificada dividindo os itens a serem classificados em duas metades de tamanho aproximadamente igual, classificando cada metade usando a classificação de mesclagem e mesclando os resultados classificados. Isso especifica completamente a idéia de classificação por mesclagem, mas não é determinística: não especifica uma ordem na qual classificar as metades (por tudo que importamos, isso pode ser feito simultaneamente), nem especifica uma maneira exata de determine a divisão. Esses detalhes precisarão ser preenchidos para chegar a uma versão seqüencial e determinística da classificação de mesclagem que pode ser implementada por um programa de computador de thread único, mas eu diria que eles fazem parte de uma maneira específica de fazer a classificação de mesclagem, não a idéia de mesclagem se classifica.

O mesmo se aplica aos algoritmos em geral - por exemplo, receitas de livros de receitas. Algumas pessoas definem algoritmos como determinísticos; nesse caso, essa noção mais geral e, na minha opinião, mais natural de 'algoritmo' precisa de um nome diferente.

A idéia de trabalhar com especificações não determinísticas foi formalizada pelo método de programação de Dijkstra, que começa por especificações que apenas fornecem pré e pós condições a serem atendidas pelo programa e desenvolve sistematicamente um programa determinístico e imperativo a partir delas. Dijkstra provavelmente teria dito: a triagem é o problema, a relação entre pré e pós-condições que estamos tentando estabelecer; mesclar classificaçãoé uma abordagem para fazer isso, algures a meio caminho entre a especificação do problema e uma solução determinística; um algoritmo determinístico de classificação de mesclagem determinístico é uma solução determinística concreta. Mas a mesma abordagem geral pode ser usada para o desenvolvimento de programas concorrentes, nos quais o eventual programa ainda não é determinístico. Tais programas podem, por exemplo, ser executados em ambientes de computação distribuídos.

reinierpost
fonte
2

Você está certo, NÃO podemos construir uma máquina não determinística. Portanto, o objetivo não é usar o conceito para construir máquinas melhores. Em vez disso, o não determinismo é um conceito útil ao tentar entender a computação. Por exemplo, agora sabemos que, do ponto de vista da computabilidade, o não determinismo não é algo mais poderoso que o determinismo, o que significa que podemos simular uma máquina não determinística usando uma determinística. No entanto, da perspectiva da complexidade, o não determinismo nos permite, por exemplo, raciocinar e tentar entender a relação entre a dificuldade de encontrar uma solução eficiente para um problema e a dificuldade de verificar uma solução (que é o famoso problema P versus NP) . E assim por diante. Portanto, a principal razão para estudar o não determinismo é teórica.

Massimo Cafaro
fonte
Livre de contexto versus determinístico Livre de contexto?
alto
@alto O que há?
babou
@babou Eu estava tentando apontar que "o não determinismo não é algo mais poderoso que o determinismo", é uma afirmação falsa. Os NPDAs são mais poderosos que os PDAs.
alto
1
@alto: não, você está entendendo mal a afirmação. Do ponto de vista da computabilidade, eles são totalmente equivalentes, já que a classe de problemas (ou idiomas, se preferir) que você pode resolver INDEPENDENTEMENTE de quantos recursos computacionais são necessários é a mesma. E, de fato, você PODE simular uma máquina não determinística com uma máquina determinística. Novamente, o tempo e o espaço requeridos NÃO IMPORTAM no contexto da computabilidade.
Massimo Cafaro
1
@MassimoCafaro Não poderia concordar mais, em teoria. Na prática, parece que prefiro discutir sobre semântica.
alto
2

a invenção da máquina de Turing foi em 1936 por Turing. Os modelos do tipo FSM foram introduzidos por McCulloch e Pitts , dois neurofisiologistas, como modelo para atividade neurobiológica em 1943. na página de história da Stanford CS :

A emocionante história de como os autômatos finitos se tornaram um ramo da ciência da computação ilustra sua ampla gama de aplicações. As primeiras pessoas a considerar o conceito de máquina de estado finito incluíram uma equipe de biólogos, psicólogos, matemáticos, engenheiros e alguns dos primeiros cientistas da computação. Todos eles compartilhavam um interesse comum: modelar o processo de pensamento humano, seja no cérebro ou em um computador. Warren McCulloch e Walter Pitts, dois neurofisiologistas, foram os primeiros a apresentar uma descrição dos autômatos finitos em 1943. Seu artigo, intitulado "Um cálculo lógico imanente na atividade nervosa", fez contribuições significativas ao estudo da teoria das redes neurais, teoria da autômatos, a teoria da computação e a cibernética. Mais tarde, dois cientistas da computação, GH Mealy e EF Moore, generalizou a teoria para máquinas muito mais poderosas em trabalhos separados, publicados em 1955-56. As máquinas de estado finito, a máquina Mealy e a máquina Moore, são nomeadas em reconhecimento ao seu trabalho.

não é um historiador de CS, mas suspeita que o modelo de McCulloch-Pitts não incluísse o não-determinismo e o modelo de Mealy - Moore , em uma generalização / abstração natural do conceito formal / teórico. observe que os DFAs e os NFAs têm o mesmo poder representacional, de modo que, se alguém deseja modelar sistemas reais, há uma opção. uma diferença básica é que um NFA pode ser muito menor que um DFA equivalente (por exemplo, existe um elemento natural da compactação de dados / informações). também existem aspectos / análogos naturais do paralelismo no estudo da NFA.

vzn
fonte
3
Ei, eu vi o seu perfil e parece que alguém intencionalmente baixa as suas respostas (em todos os lugares onde você tem apenas dois votos negativos ) ... Essa resposta não está errada , a resposta adiciona informações úteis. +1
Grijesh Chauhan
0

Em primeiro lugar, gostaria de agradecer a todas as pessoas que responderam à pergunta.Todas as respostas são importantes e acrescentam algumas informações úteis.Mas como é uma pergunta complicada para os iniciantes, e precisam de tempo suficiente para entendê-la bem, tentaria resumir o que ganhei de todas as respostas e de alguns livros:

Na verdade, eu tinha uma confusão que era sobre o mecanismo do modelo não determinístico. Eu sempre me perguntei sobre a máquina não determinística, pois é uma máquina não mecânica que não existe no mundo real. Sempre comparei o Automata com nossos computadores atuais, que são completamente determinísticos por natureza. Na verdade, eu não estava entendendo corretamente o modelo não determinístico. Agora, acho que estou entendendo muito bem o modelo não-minimalista: uma máquina não-determinística é uma máquina que sempre segue esse caminho de execução que leva à aceitação da string (sem retroceder). Mas como isso pode ser possível na vida real? : É absolutamente impossível para o computador atual ser tão inteligente em prever o futuro. Então, por que não-determinismo? A resposta a esta pergunta é bastante complicada.O que concluí sobre a pergunta é que: A teoria dos autômatos existia quando os computadores não existiam (primeira teoria então prática). É assunto puramente teórico e o conceito de não-determinismo surgiu intuitivamente. O motivo do assunto "Teoria dos autômatos" não era lidar com computadores práticos. Mas quando praticamente o computador chega e, usando a Teoria dos Automatizados, somos capazes de definir computadores práticos com precisão: quais são as limitações dos computadores atuais.que problema algorítmico é muito complexo para os computadores e é tão impraticável (aqui, o papel do não -ERMERMINISMO é muito crucial pelo qual pode distinguir duas classes de complexidade P e NP). Quais são as soluções para esses problemas impraticáveis ​​pelos quais ele pode ser executado comparativamente mais rápido.etc. Essa é a utilidade do não-determinismo. É assunto puramente teórico e o conceito de não-determinismo surgiu intuitivamente. O motivo do assunto "Teoria dos autômatos" não era lidar com computadores práticos. Mas quando praticamente o computador chega e, usando a Teoria dos Automatizados, somos capazes de definir computadores práticos com precisão: quais são as limitações dos computadores atuais.que problema algorítmico é muito complexo para os computadores e é tão impraticável (aqui, o papel do não -ERMERMINISMO é muito crucial pelo qual pode distinguir duas classes de complexidade P e NP). Quais são as soluções para esses problemas impraticáveis ​​pelos quais ele pode ser executado comparativamente mais rápido.etc. Essa é a utilidade do não-determinismo. É assunto puramente teórico e o conceito de não-determinismo surgiu intuitivamente. O motivo do assunto "Teoria dos autômatos" não era lidar com computadores práticos. Mas quando praticamente o computador chega e, usando a Teoria dos Automatizados, somos capazes de definir computadores práticos com precisão: quais são as limitações dos computadores atuais.que problema algorítmico é muito complexo para os computadores e é tão impraticável (aqui, o papel do não -ERMERMINISMO é muito crucial pelo qual pode distinguir duas classes de complexidade P e NP). Quais são as soluções para esses problemas impraticáveis ​​pelos quais ele pode ser executado comparativamente mais rápido.etc. Essa é a utilidade do não-determinismo. Mas quando praticamente o computador chega e, usando a Teoria dos Automatizados, somos capazes de definir computadores práticos com precisão: quais são as limitações dos computadores atuais.que problema algorítmico é muito complexo para os computadores e é tão impraticável (aqui, o papel do não -ERMERMINISMO é muito crucial pelo qual pode distinguir duas classes de complexidade P e NP). Quais são as soluções para esses problemas impraticáveis ​​pelos quais ele pode ser executado comparativamente mais rápido.etc. Essa é a utilidade do não-determinismo. Mas quando praticamente o computador chega e, usando a Teoria dos Automatizados, somos capazes de definir computadores práticos com precisão: quais são as limitações dos computadores atuais.que problema algorítmico é muito complexo para os computadores e é tão impraticável (aqui, o papel do não -ERMERMINISMO é muito crucial pelo qual pode distinguir duas classes de complexidade P e NP). Quais são as soluções para esses problemas impraticáveis ​​pelos quais ele pode ser executado comparativamente mais rápido.etc. Essa é a utilidade do não-determinismo. Quais são as soluções para esses problemas impraticáveis ​​pelos quais ele pode ser executado comparativamente mais rápido.etc. Essa é a utilidade do não-determinismo. Quais são as soluções para esses problemas impraticáveis ​​pelos quais ele pode ser executado comparativamente mais rápido.etc. Essa é a utilidade do não-determinismo.

Por favor, corrija-me se houver algo errado.

tanmoy
fonte
É errado dizer que uma máquina não determinística é uma máquina que sempre segue o caminho da execução que leva à aceitação da string . Não faz isso! Uma máquina não determinística é uma máquina cuja operação permite que certas escolhas não-premeditadas (= não-determinísticas) sejam feitas durante a execução. Não há nada de irreal nessas máquinas, por exemplo, elas podem solicitar ao ambiente que faça essas escolhas. Essas máquinas são então aplicadas a tarefas para as quais considera que certas opções produzirão um estado de aceitação.
Reinierpost
@reinierpost: Então você está dizendo que máquinas não determinísticas existem na vida real.
Tanmoy
Sim. Aqui está um exemplo: suponha que você esteja dirigindo um carro e não tome nenhuma decisão no caminho a seguir. Por exemplo, você pode dirigir sem rumo, ou pode seguir as instruções de um navegador humano ou de um dispositivo de navegação. O carro e você são um sistema não determinístico para dirigir lugares. Você se move no trânsito e continua encontrando opções em que direção tomar. Para você e para o carro, essas escolhas não são determinísticas: você não está decidindo qual direção seguir, mas, dada essa decisão, você a seguirá.
Reinierpost
@reinierpost: Existe algum computador não determinístico? Minha resposta é NÃO. porque, se existir, os problemas de NP teriam complexidade de tempo polinomial. não é?
tanmoy
Se os computadores são determinísticos ou não determinísticos, depende de como você os vê. Quando um computador para e espera que o usuário faça alguma coisa, e suas próximas ações dependerão do que o usuário fizer, você pode dizer que é uma escolha não determinística. Não, isso não implica que P = NP.
Reinierpost
0

o não determinismo é útil porque ajuda a entender o determinismo, mas não o contrário. Você poderia dizer que o não-determinismo é a idéia maior. Uma máquina de turbulência determinística é um caso especial de uma não determinística. - O não determinismo pode nos ajudar a entender por que, nas plataformas atuais, alguns problemas são difíceis de identificar. Existem vários problemas computacionais que não têm solução eficiente em uma plataforma de computação determinística, mas entendemos que pode haver soluções eficientes em problemas não determinísticos. ... estado, codificação, não determinismo, todos eles estão vinculados http://people.cs.umass.edu/~rsnbrg/teach-eatcs.pdf

Em uma máquina determinística de Turing, o conjunto de regras prescreve no máximo uma ação a ser executada para qualquer situação. Uma máquina de Turing não determinística (NTM), por outro lado, pode ter um conjunto de regras que prescreve mais de uma ação para uma determinada situação. http://en.wikipedia.org/wiki/Non-deterministic_Turing_machine Se você pode criar uma caixa de software que possa gerenciar tão bem as transições de estado que possa lidar com mais de uma ação, poderá obter desempenho além das máquinas determinísticas.

Tom
fonte
Não sei se os supostos links para a realidade são úteis. É bastante claro que não podemos construir uma máquina não determinística (pelo menos hoje), por isso é uma construção totalmente teórica.
Raphael
Podemos construir uma máquina não determinística, deixando que as decisões não determinísticas sejam tomadas por algo externo à máquina.
reinierpost
@ reinierpost, mais importante, podemos construir máquinas não determinísticas como determinísticas, sem incorrer em despesas exponenciais. veja o Teorema de Savitch. en.wikipedia.org/wiki/Savitch's_theorem
Tom
@ Rafael, algumas referências ao mundo real são importantes. Por que o cache funciona? Porque os eventos no mundo real, que são a fonte de todos os dados, seguem uma distribuição normal. consulte Localidade temporal: durablescope.blogspot.co.at/2009/11/…
Tom
@ reinierpost, e que algo externo é o que Turing chamou de máquina oracle. Eu acho que você pode pensar se isso é como dados saindo do cache ou algo parecido com uma máquina com várias fitas ou mesmo acessando a memória de acesso aleatório.
Tom
0

Por que o não-determinismo é um conceito útil?

O determinismo tem uma forte tendência a quebrar simetrias. Essa tendência é ainda mais forte para o determinismo seqüencial, mas a noção de um gráfico direcionado acíclico e uma ordem topológica desse gráfico permite ignorar a diferença entre determinismo e determinismo seqüencial. O não determinismo é um superconjunto de determinismo, que permite preservar mais simetrias. Ao projetar a solução de um problema, começar com a solução não determinística permite preservar simetrias úteis, e que mantém a descrição da solução pequena e compacta. A quebra das simetrias pode ser delegada para um estágio posterior durante a implementação, enquanto converte a solução não determinística em uma solução determinística.

Frequentemente, o não determinismo significa que a noção de uma função parcial é substituída pela noção de uma relação. Nesse caso, uma máquina não determinística pode correr para frente e para trás no tempo, enquanto isso não é possível em geral para uma máquina determinística. Se trabalharmos com funções totais para determinismo e funções totais com valores múltiplos para não determinantes, a simetria não é mais tão boa, mas ainda pode ser feita para funcionar.

Thomas Klimpel
fonte
Você pode dar um exemplo específico? Acho difícil ver o que você quer dizer com "simetria" aqui.
Raphael
@Raphael Que tal reverter (01) * 01 (0 + 1) * para (0 + 1) * 10 (10) * de modo que reconheça a sequência de entrada invertida e aplique essa simetria à máquina não determinística revertendo tudo seta e troca de estado inicial e final? Não tenho certeza se existem exemplos significativamente mais interessantes para máquinas de estados finitos, mas eu poderia tentar criar um exemplo interessante para um PDA.
Thomas Klimpel
Escrevi sobre minha resposta a uma pergunta semelhante em um post de blog sobre Reversibilidade de relações binárias, matrizes sub-fasásticas e funções parciais .
Thomas Klimpel