Máquina de Turing não determinística que para em pelo menos um ramo da computação

Estou vendo meu livro aqui, de Michael Sipser, e ele diz que uma máquina de Turing não determinística é decisiva se todos os seus ramos de computação pararem em todas as entradas. Acho que me lembro de ter visto em algum lugar o que você chamaria de máquina de Turing não determinística que pára em pelo menos um ramo para todas as entradas, mas pode se repetir em outras. Existe um nome para uma coisa dessas? Vejo mais adiante neste capítulo o verificador de palavras , mas isso não parece se encaixar ... Acho que isso se refere a um algoritmo.

Um verificador para uma linguagem é um algoritmo , em que Nós medimos o tempo de um verificador apenas em termos do comprimento de , portanto, um verificador de tempo polinomial é executado em tempo polinomial no comprimento de . Uma linguagem é polinomialmente verificável se tiver um verificador de tempo polinomial.$A$$V$

$$A=\{w\mid V\text{ accepts }\langle w,c\rangle\text{ for some string c}\}.$$ $w$$w$$A$

A idéia é que uma MT determinística sempre responda Sim / Não em tempo finito (caso contrário, toda a idéia não faz sentido). E para fazer isso, a simulação determinística do MNT não pode simplesmente ir para a terra da terra em alguns galhos, ou seja, todo galho deve terminar em sim / não em uma profundidade finita. Ele decide (dá uma resposta definitiva). Se nem todos os ramos pararem, é possível verificar (ou seja, dada uma palavra no idioma, é garantido que ele responde Sim; se não, talvez responda Não, talvez faça um loop).

As strings aceitas por um NTM Msão o idioma de M, observadoL(M)

Digamos que, Mpara qualquer entrada, não há garantia de interrupção em todos os ramos. Então Mclaramente não pode ser um decisor e, portanto, é apenas um reconhecedor. Mreconhece o idioma de todas as strings, para as quais qualquer ramo Mtermina em um estado de aceitação.

Desde Mé um reconhecedor, ele só é garantido para aceitar uma string se a cadeia está em L(M). Dada uma sequência, que não está presente L(M), ela pode rejeitá-la ou fazer um loop para sempre. Qualquer NTM pode ser simulado por um DTM, mas se o NTM reconhecer apenas um idioma L, seu DTM equivalente também reconhecerá apenas L.

Se o NTM parar em todas as ramificações para qualquer entrada, é uma decisão, o DTM equivalente fará o mesmo e, portanto, também será uma decisão.

Um verificador não é o que você está procurando. No livro Sipsers, Introdução à teoria da computação, o verificador é introduzido quando se fala em complexidade de algoritmos e classes de complexidade, porque qualquer linguagem Lestá no NP se e somente se tiver um verificador de tempo polinomial.

Um verificador para uma linguagem Lterá como entrada uma string wem Le um certificado c(pense o certificado como uma solução para o problema w) e verificar se o certificado é de fato uma solução correta, o que torna wmentira L.

Exemplo:

Para o idioma

L = { w | w is an integer for which the product of some of the digits equals 12000 }

Você pode fazer um verificador V, que leva uma corda wem Lum certificado c, e verifica se wé, de fato, em Lutilizando o certificado c. cpoderia ser uma sequência binária indicando os números inteiros wpara os quais o produto é igual a 12000.

Por exemplo, Vdeve rejeitar a entrada 1923423343, 0010111011, porque2*4*2*3*4*3 = 576 != 12000

Para muitos problemas, conhecemos apenas um algoritmo que pode resolvê-los em execução no tempo exponencial do tamanho da entrada. É por isso que os verificadores são interessantes, porque geralmente é o caso, que fornecemos uma solução rapidamente para determinar se essa solução está correta ou errada.