¿Cómo puedo aplicar el teorema de Rice?

Question

Estoy aprendiendo para mi examen de computabilidad y complejidad en el que siempre hay un ejercicio para decidir si algún problema es decidible o no.

En uno de los exámenes pasados, hubo el siguiente problema:

Máquina de Turing M, decida si existe un número primo en el que se detiene.

Se supone que debo decidir si el problema es decidible o no.

Supongo que puedo reescribir el problema en el idioma $ l={\ langle m \ rangle | \ existe p \ in \ mathbb {p}: m (p) \ downrow \} $ . Me han dado un indicio de que puedo usar el teorema de Rice para demostrar que el idioma es indecidible. En realidad, estoy luchando, ya que no tengo idea de cómo debo aplicar el teorema de Rice a (Generaly cualquier) problema.

Estoy interesado en estas preguntas:

1. ¿Cómo puedo averiguar si el teorema de Rice es aplicable o no?
2. Si lo encuentro, ¿cómo aplicarlo? (En este ejercicio en particular)

Cualquier ayuda apreciada.

Answer 1

Aquí hay otra técnica de prueba elemental que no utiliza el teorema de Rice, que está muy exagerado para este simple problema.

Turing Turing Machine Family $ f (a) $ que entra en un bucle infinito para cualquier entrada, excepto 2, en cuyo caso se ejecutará el programa $ A $ , que puede ser arbitrario.

Ahora, si pudiéramos decidir su problema original, podríamos decidir por las máquinas de Turing de entrada arbitrarias, ya sea que se detendrán usando $ f $ .Pero esto es obviamente indecidible y, por lo tanto, su problema original también es.