Síntese do programa, decidibilidade e o problema da parada

11

Eu estava lendo uma resposta para uma pergunta recente, e uma espécie de pensamento estranho e efêmero veio à minha mente. Pedir isso pode revelar que minhas faltas teóricas estão seriamente ausentes (principalmente verdadeiras) ou que ainda é muito cedo para ler este site. Agora, com o aviso fora do caminho ...

É um resultado bem conhecido a teoria da computabilidade de que o problema da parada não pode ser decidido para as MTs. No entanto, isso não exclui a possibilidade de existirem máquinas que possam resolver o problema de parada de determinadas classes de máquinas (apenas não todas).

Considere o conjunto de todos os problemas decidíveis. Para cada problema, existem infinitas TMs que decidem esse idioma. Poderia ser possível o seguinte

  • Existe uma TM que decide o problema de parada para um subconjunto de máquinas de Turing; eS
  • Todos os problemas decidíveis são decididos por pelo menos uma máquina de Turing em ?S

Obviamente, encontrar a máquina de Turing em pode não ser computável; mas ignoramos esse problema.S

EDIT: Com base na resposta de Shaull abaixo, parece que (a) essa idéia é muito mal especificada para ser significativa ou (b) minha tentativa anterior não foi totalmente correta. Como eu tento elaborar nos comentários a resposta de Shaull, minha intenção não é que estamos garantiu que o TM entrada está em . O que realmente quis dizer com a minha pergunta é se poderia existir um S , de tal forma que a associação a S seja um problema decidível . O programa para resolver o problema de parada de S gravaria, presumivelmente, "entrada inválida" na fita ou algo assim, quando receber uma entrada que reconheça como não estando em SSSSSS. Quando o formulo dessa maneira, não tenho certeza se isso nos permite resolver o problema da parada ou não, ou se o teorema de Rice se aplica (a decidibilidade é uma propriedade semântica de uma linguagem com base no teorema de Rice?)

turing-machines undecidability halting-problem Patrick87
fonte
acho que há uma questão legítima / significativa nos limites da teoria oculta aqui em algum lugar, mas não na forma atual, no entanto, +1 por tentar [e esse aviso no início é surpreendente, considerando seu status de representante / moderador] ... talvez seja esse a pergunta que você estava lendo? algoritmo para resolver turings problema da parada
vzn
possivelmente outra maneira de formular a pergunta, não sei se essa foi a intenção (o que a torna muito avançada). considere todos os possíveis "quase-algoritmos" e seus conjuntos reconhecidos associados . [veja outra pergunta para defns]. a união de todos esses conjuntos reconhecidos S n é igual ao conjunto de todas as TMs recursivas / decidíveis? SnSn
vzn

Respostas:

7

Eu acho que pode haver um problema com a formulação do problema.

Considere o conjunto é um determinante de seu idioma } . O problema da parada é decidível para este conjunto (ou seja, se formos prometidos que a entrada está nesse conjunto). De fato, é trivial (as máquinas em S sempre param).S={M:M}S

Além disso, claramente todas as línguas decidable está em .S

EDIT: Com base nas mudanças na pergunta - de fato, a participação em seria indecidível: se S contiver uma máquina para cada idioma decidível, então S ≠ ∅ . Assim, pelo teorema de Rice, se S é decidível, então S contém todas as máquinas, mas depois o problema da parada é indecidível em S .SSS≠∅SSS

Shaull
fonte
Em outras palavras, trivialmente responde positivamente à pergunta. S={⟨UMA⟩∣∀x.UMA(x)↓,eu(UMA)∈R}
Raphael
1
@ Rafael - não, porque enquanto , isso não implica que A seja uma decisão. É por isso que explicitamente tomamos decisões. eu(UMA)∈RUMA
quer
1
Ah, certo. Corrigido o comentário.
Raphael
+1 Não tenho certeza se comuniquei claramente meu significado. O que eu realmente queria dizer para perguntar era se é possível que tal existe, e podemos verificar uma arbitrária TM para ver se ele está em S . Não sabemos a priori que esteja em S ; apenas que S é formulado de tal maneira que podemos verificar. Em outras palavras, é possível que exista um S de modo que a participação em S seja decidível? Além disso, sua última frase é um pouco confusa; S é um conjunto de máquinas de Turing (bem, suas representações); não das línguas que as TMs decidem ... mas acho que sei o que você quer dizer.SSSSSSS
precisa saber é o seguinte
1
(ps Desculpe sobre começar seu nome errado em minhas edições Seu ser muito cedo para eu fazer CS.SE está começando a aparecer cada vez mais provável.)
Patrick87