0
$\begingroup$

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:

  1. How can I find out whether Rice's theorem is applicable or not?
  2. If I find it out, how to apply it? (In this excercise in particular)

Any help appreciated.

$\endgroup$
1
$\begingroup$

Here's another, elementary proof technique that does not use Rice's theorem which is way overkill for this simple problem.

We have Turing machine family $F(A)$ that goes into an infinite loop for any input except 2, in which case it will run program $A$, which can be arbitrary.

Now if we could decide your original problem we could decide for arbitrary inputless Turing machines whether they halt using $F$. But this is obviously undecidable and therefore your original problem is as well.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.