Por que o problema da parada é semi-decidível?

7

É o que se sabe sobre o problema da parada e a semi-decidibilidade:

O problema de parada diz que, para uma dada entrada xe uma máquina H, não podemos dizer se a máquina H pára ou não na entrada x.

Diz-se que um idioma é semi-decidível se existir uma máquina de Turing que pare se uma palavra pertencer ao idioma (casos SIM) e pode rejeitar ou entrar em loop infinito se a palavra não pertencer ao idioma (caso NÃO) .

Agora, no problema de parada, não podemos dizer se a máquina irá parar, mesmo que a entrada pertença ao idioma (casos YES). Então, como é semi-decidível? Eu acho que deveria ser não recursivamente enumerável ou indecidível.

computability turing-machines halting-problem semi-decidability Zephyr
fonte
"Agora, no problema de parada, não podemos dizer se a máquina irá parar, mesmo que a entrada pertença ao idioma" Por que não? A máquina precisa parar para aceitar a palavra. Também não tenho certeza de que exista algo semidecidível. Eu só sei decidível ou indecidível. O problema da parada é indecidível.
Usuário não encontrado
2
Observe que isso não tem nada a ver com o teste de Turing.
Raphael
@ArghyaChakraborty Semi-decidível significa que, para qualquer problema, existe uma máquina de Turing para esse problema que sempre terminará para a entrada aceita, mas terminará ou não para todas as outras entradas. (Opa, acabei de perceber que o OP escreveu), é uma coisa.
Micrified
@ Ok, agora você está me confundindo ... a próxima afirmação é verdadeira? "Agora, no problema de parada, não podemos dizer se a máquina irá parar, mesmo que a entrada pertença ao idioma"
User Not Found
@ArghyaChakraborty Estou apenas dizendo a você que o termo "Semi-Decidable" é válido e fazendo eco ao que o OP o definiu. Se você quiser me perguntar sobre o problema da interrupção em relação a essa palavra, então eu também posso responder. "Agora, no problema de parada, não podemos dizer se a máquina irá parar, mesmo que a entrada pertença ao idioma": False. Qualquer máquina no idioma de parada sempre terminará para a entrada pertencente ao idioma.
Micrified

Respostas:

15

Tl; dr: "(diga) se pára ou não" e "(diga) se pára" não são a mesma coisa. Use a matemática para evitar confusão induzida pela ambiguidade da linguagem.

O problema de parada diz que, para uma dada entrada xe uma máquina H, não podemos dizer se a máquina H pára ou não na entrada x.

Não, não é isso que diz. O problema da parada é o problema computacional de decidir seH pára x, dado x e Hcomo entrada. É importante notar que "decidir" aqui significa "diga sim se for assim e diga não se não for".

A indecidibilidade do problema de parada afirma que não existe um algoritmo único (máquina de Turing) que resolve o problema de parada para todos H e x.

Agora, no problema de parada, não podemos dizer se a máquina irá parar, mesmo que a entrada pertença ao idioma (casos YES). Então, como é semi-decidível?

Após o esclarecimento acima, sua confusão aqui deve ficar clara. Não importa o que "podemos dizer". O "problema de semi-parada" é relaxado: o algoritmo ainda precisa dizer "sim" seH pára x, mas pode fazer o que quiser, se não o fizer (exceto a resposta "sim").

Isso é trivial de implementar: basta executar H em x. Se parar, responda "sim". Caso contrário, não importa, pois temos permissão para fazer um loop.

Rafael
fonte
Então, a declaração que escrevi sobre o problema de parada foi, na verdade, sobre a indecidibilidade de parar o problema? De acordo com você, o problema de semi-parada é recursivamente enumerável e, portanto, semi-decidível. Então, o problema real da parada é indecidível e não semi-decidível? Lamento se estou fazendo perguntas triviais, sou novo nisso.
Zephyr
"Então, a declaração que escrevi sobre o problema de parada foi, na verdade, sobre a indecidibilidade de parar o problema?" -- sim. No TCS, "problema" é técnico, não deve ser confundido com a palavra inglesa normal. Veja também aqui . "Então, o problema real da parada é indecidível e não semi-decidível?" - Não. Fui um pouco informal lá (daí as aspas): é o problema da parada, mas expresso em termos de semi-decidibilidade. O problema da parada é indecidível, mas semi-decidível.
Raphael
De acordo com o que você disse sobre indecidibilidade, não há algoritmo que resolva o problema de parada para todos os H e x, o que significa que nenhum algoritmo pode decidir se H pára em x, considerando x e H como entrada. Portanto, mesmo se fornecermos uma entrada pertencente à linguagem, o algoritmo não pode decidir se será interrompido, portanto deve ser completamente indecidível.
21817 Zephyr
11
Não existe algo como "completamente indecidível". E não, nenhum algoritmo pode decidir , mas ainda pode semi-decidir. Essas são noções diferentes; você deve verificar as definições formais. Analogia intuitiva: até depois da sua morte, você nunca pode dizer com confiança "nunca um cocô de toupeira na minha cabeça". Mas se isso acontecer, você pode afirmar com absoluta certeza "uma toupeira cocô na minha cabeça".
Raphael
4
Se a questão de parar é indecidível, isso não significa que às vezes não posso decidir se isso pára. Em casos de interrupção, posso decidir que eles param apenas esperando até que parem. Para casos sem interrupção, às vezes posso fornecer uma prova de que eles não param e que os decide.
gnasher729