Como posso aplicar o teorema do arroz?

Question

Eu estou aprendendo para o meu exame de computação e complexidade nos quais há sempre um exercício para decidir se algum problema é decidível ou não.

Em um dos exames anteriores, houve o seguinte problema:

Dada a máquina de Turing M, decida se existe um número primo no qual M pára.

Eu devo decidir se o problema é decidível ou não.

Eu acho que posso reescrever o problema na linguagem $ l= {\ langle m \ rangle | \ existe p \ in \ mathbb {p}: m (p) \ DOWARROW \} $ . Eu recebi uma dica que posso usar o teorema do arroz para provar que a linguagem é indecável. Eu estou realmente lutando, já que não tenho ideia de como devo aplicar o teorema de arroz (generaly qualquer) problema.

Estou interessado nestas perguntas:

.
1. Como posso descobrir se o teorema de arroz é aplicável ou não?
2. Se eu descobrir, como aplicá-lo? (Neste exercício em particular)

Qualquer ajuda apreciada.

Answer 1

Aqui está outra técnica de prova elementar que não usa o teorema do arroz que é um exagero para este problema simples.

nós temos a família da máquina de Turing $ f (a) $ que entra em um loop infinito para qualquer entrada, exceto 2, caso em que será executado programa $ a $ , que pode ser arbitrário.

Agora, se pudéssemos decidir seu problema original, poderíamos decidir por máquinas de Turing sem instruções arbitrárias, se eles param usando $ F $ .Mas isso é obviamente indecidável e, portanto, seu problema original é também.