I am learning for my computability and complexity exam in which there is always an exercise to decide whether some problem is decidable or not.
In one of the past exams, there was the following problem:
Given Turing Machine M, decide whether there exists a prime number on which M halts.
I am supposed to decide whether the problem is decidable or not.
I guess I can rewrite the problem into the language $L = \{ \langle M \rangle | \exists p \in \mathbb{P} : M(p) \downarrow \}$. I have been given a hint that I can use Rice's theorem to prove the language is undecidable. I am actually struggeling, since I have no idea how should I apply Rice's theorem to (generaly any) problem.
I am interested in these questions:
- How can I find out whether Rice's theorem is applicable or not?
- If I find it out, how to apply it? (In this excercise in particular)
Any help appreciated.