Como funciona uma máquina de Turing não determinística?

12

Quais são as diferenças entre as máquinas de Turing determinísticas e não determinísticas? Modelos diferentes, mas equivalentes, do NDTM. Em particular, qual é a frase usada com frequência "adivinhação não-determinística"? Como usá-lo corretamente e exemplos de uso incorreto. Meu objetivo é criar uma pergunta de referência.

fade2black
fonte
1
O que você está procurando além do que a Wikipedia tem a dizer sobre o assunto?
David Richerby
1
Minhas contribuições sobre este assunto: um , dois .
Raphael
Não sei se concordo com a forma dessa tentativa de uma pergunta de referência (bastante ampla). Além disso, não está claro para mim o que além da definição é esperado aqui. (Se mais pessoas iria ler a definição, haveria menos confusão em torno.)
Raphael

Respostas:

8

Aqui estão várias maneiras de pensar sobre o não-determinismo (copiado desta resposta ).

O gênio. Sempre que a máquina tem escolha, um gênio diz a ela que caminho seguir. Se a entrada estiver no idioma, o gênio poderá direcionar a máquina de tal maneira que eventualmente aceite. Por outro lado, se a entrada não estiver no idioma, o que quer que o gênio diga à máquina para fazer, ela sempre será rejeitada.

Dicas. A máquina calcula uma função bivariada. A primeira entrada é uma palavrawe a segunda entrada é uma "dica" x. Sempre que a máquina enfrenta uma escolha não determinística, ela consulta o próximo símbolo de dica e opera em conformidade. Nos é prometido o seguinte:

  • Completude: sewL então há alguma dica x o que faz com que a máquina aceite.
  • Solidez: sewL então a máquina rejeita todas as dicas.

Aceitando cálculos. Um cálculo de aceitação é um cálculo legal (aquele em que a máquina sempre opera de acordo com uma das opções com que se depara) que termina em um estado de aceitação. Uma palavra está no idioma se tiver um cálculo aceitável.

Podemos formalizar a noção de aceitar computação usando configurações . Uma configuração é uma descrição instantânea de todo o estado da máquina. Podemos definir uma relaçãoσσ, Onde σ,σ são configurações, que são mantidas quando σ pode levar a σem uma etapa. Em uma máquina determinística, há no máximo umaσ por cada σ, enquanto que em uma máquina não determinística, pode haver mais de uma. Um cálculo de aceitação para uma palavraw é aquele que inicia na configuração inicial (a fita contém w, a cabeça aponta no início de w, o estado é o estado inicial) e termina em uma configuração de aceitação.

Outra descrição equivalente é em termos de acessibilidade. Considere um gráfico direcionado no qual os vértices são configurações e existe uma arestaσ para σ E se σσ. Um cálculo de aceitação é um caminho da configuração inicial para uma configuração de aceitação.

Yuval Filmus
fonte
7

A diferença entre as máquinas de Turing determinística e não determinística está na função de transição. Em máquinas determinísticas de Turingδ a função de transição é uma função parcial:

δ:Q×BQ×B×{left,right}

o que significa que, dado um estado e um símbolo de fita, você tem um ou nenhum estado, insira o símbolo à direita e a direção a se mover. No entanto, em máquinas de Turing não determinísticas, isso se parece (aquiP é o conjunto de subconjuntos de um conjunto):

δ:Q×BP(Q×B×{left,right})

significando que você tem um ou vários estados, símbolos de fita para escrever ou direção para a qual mover. Isso dá à sua máquina a possibilidade de escolher efetivamente nesse estado e símbolo de fita entre os diferentes "ramos" da computação possíveis.

Na prática, isso significa que podemos calcular saídas diferentes para a mesma entrada. Portanto, a linguagem de uma máquina de Turing não determinística é o conjunto de palavras para as quais encontramos uma derivação nas transições definidas. Uma execução específica pode não encontrar essa derivação, mas o importante é que ela possa ocorrer. Então, quando você "adivinha", está apenas escolhendo um dos possíveis ramos da computação.

Exemplo de uso

L={(M1,M2):there exists at least one word accepted by both TM at the same time}

Nesse caso, é possível "adivinhar" uma palavra w e executar M1 e M2 em wverificando se ambos aceitam, eles aceitam ao mesmo tempo. A suposição poderia funcionar introduzindo um estadoq com transições que escrevem em alguma fita 0se / ou 1se sai lendo qualquer símbolo na máquina geral.

Para ser honesto, não encontrei nenhum exemplo de mau uso desse "palpite", mas verificar se cada vez que essa frase é usada corretamente é reduzido, para verificar se você pode construir um autômato com essa estrutura que simula o palpite.

Rodrigo
fonte
"Na prática, isso significa que podemos calcular resultados diferentes para a mesma entrada". - isso parece sugerir que poderíamos realmente construir uma máquina não determinística. Isso é falso.
Raphael
@ Rafael, você quer dizer que não é possível construir uma máquina não determinística? porque é esse o caso?
Rodrigo Rodrigo
Porque o não determinismo é um conceito matemático que não tem um equivalente físico (tanto quanto eu sei).
Raphael
6

Aceitação da sequência de entrada no NTM

deixe-me acrescentar mais sobre máquinas de Turing determinísticas e não determinísticas. Vamos considerar que, para algum idiomaL, projetamos uma máquina de Turing determinística e não determinística, respectivamente. Em alguma entradax, haverá apenas um caminho de configurações no caso da máquina determinística de Turing, ou seja, c0c1ck (onde cada ci representa uma configuração em ipasso). Agora com base na configuraçãock, podemos aceitar e rejeitar facilmente a sequência de entrada x.

Veja a imagem abaixo para entender melhor: insira a descrição da imagem aqui

No caso do NTM, precisamos ter cuidado, pois pode acontecer que em alguns caminhos de configuração, entremos no estado de rejeição. Portanto, para máquinas de Turing não determinísticas, dizemos que uma string é aceita se pelo menos um dos caminhos de configuração levar ao estado de aceitação . Rejeitaremos a sequência de entrada se todos os caminhos de configuração levarem ao estado de rejeição.

Por exemplo, considere a árvore de configuração fornecida acima para a máquina de Turing não determinística, digamos, alguma string de entrada xNesse caso, aceitaremos a string de entrada porque existe um caminho de aceitação.

Referência : http://cs.umw.edu/~finlayson/class/fall14/cpsc326/notes/24-complexity2.html

Shiv
fonte
5

Aumento com um módulo de adivinhação.

Encontrei esse modelo em " Computers and Intratability ", de MR Garey e DS Johnson.

O NDTM tem exatamente a mesma estrutura que um DTM, exceto pelo fato de ser aumentado com um módulo de adivinhação que possui seu próprio cabeçote de gravação. O módulo de adivinhação fornece os meios para anotar a "adivinhação" e é usado apenas para esse fim.

insira a descrição da imagem aqui

Como funciona.

O primeiro estágio é o estágio de adivinhação. Inicialmente, a sequência de entradax está escrito em quadrados de fita 1 através |x| (enquanto todos os outros quadrados estão em branco), a cabeça de leitura / gravação está digitalizando 1, a cabeça de gravação está digitalizando 1, e o controle de estado finito é "inativo". O módulo de adivinhação então direciona a cabeça somente para gravação, um passo de cada vez, para escrever algum símbolo do alfabeto da fita Γ no quadrado da fita sendo digitalizado e mova um quadrado para a esquerda ou para parar, quando o módulo de adivinhação se torna inativo e o controle de estado finito é ativado no estado q0. A escolha de permanecer ativo e, em caso afirmativo, qual símbolo deΓescrever, é feita pelo módulo de adivinhação de maneira totalmente arbitrária. Assim, o módulo de adivinhação pode escrever qualquer string deΓ antes que pare e, de fato, nunca precise parar.

O estágio de "verificação" começa quando o controle de estado finito é ativado no estado q0. A partir deste ponto, o cálculo prossegue apenas sob a direção do programa NDTM, de acordo com exatamente as mesmas regras de um DTM. O módulo de adivinhação e seu cabeçote somente para gravação não estão mais envolvidos, tendo cumprido seu papel escrevendo a sequência de caracteres adivinhada na fita. Obviamente, a corda adivinhada pode (e geralmente será) examinada durante o estágio de verificação. A computação cessa quando e se o controle de estado de estado finito entra em um dos dois estados de parada (qY ou qN) e diz-se estar aceitando computação se parar no estadoqY. Todos os outros cálculos, parando ou não, são classificados juntos simplesmente como cálculos que não aceitam .
Observe que qualquer programa NDTMM terá um número infinito de cálculos possíveis para uma determinada sequência de entrada x, um para cada sequência de caracteres possível Γ. Dizemos que o programa NDTMM aceita x se pelo menos um deles for um cálculo aceitável.

O tempo necessário para um programa NDTMM para aceitar a string xLM é definido como o mínimo, considerando todos os cálculos de M para x , do número de etapas que ocorrem nas etapas de adivinhação e verificação até o estado de parada qY é introduzido.

O único ponto que merece menção especial é que, em que geralmente imaginamos um algoritmo não determinístico como adivinhar uma estrutura S que de alguma forma depende da instância [problem] especificada I, o módulo de adivinhação de um NDTM desconsidera completamente a entrada fornecida. No entanto, uma vez que cada string deΓComo um palpite possível, sempre podemos projetar nosso programa NDTM para que o estágio de verificação comece verificando se a string adivinhada corresponde (sob a interpretação implícita que nosso programa coloca nas cordas) a uma palpite apropriada para a entrada fornecida. Caso contrário, o programa pode entrar imediatamente no estado de paradaqN.

. . .

A classe NP é definido informalmente para ser a classe de todos os problemas de decisão Π que, sob esquemas de codificação razoáveis, pode ser resolvido por algoritmos não determinísticos de tempo polinomial.

O uso do termo "resolver" nessas definições informais deve, é claro, ser tomado com um grão de sal. Deve ser evidente que um "algoritmo não determinístico de tempo polinomial" é basicamente um dispositivo de definição para capturar a noção de verificabilidade do tempo polinomial, em vez de um método realista de solução de problemas de decisão. Em vez de ter apenas um cálculo possível em uma determinada entrada, ele tem muitos diferentes, um para cada palpite possível.

É essa noção de "verificabilidade" do tempo polinomial que a classe NPdestina-se a isolar. Observe que a verificabilidade do tempo polinomial não implica solvabilidade polinomial.

fade2black
fonte