1

Let M be a machine that takes a natural number as input and outputs a natural number.
Let L = $\{M:\;M(n)\;outputs\;a\;prime\;greater\;than\;n\;for\;every\;n\}$

Is L decidable?
Is L recognizable?

Intuitively, my thoughts are that L is neither recognizable or decidable since any algorithm to decide/recognize L would have to test an infinite set of inputs.

However, I'm not sure how to reduce the Halting Problem to this problem to prove that. I'm not even sure if that is the appropriate method of proof. Can someone help?

user137481
  • 2,605

1 Answers1

0

$L$ is not recognizable (hence not decidable either):

Suppose $L$ is recognizable. Construct $M_{e,x}$ as follows: take an input $n$ and simulate the computation of $\phi_e(x)$ (where $\phi_e$ is a Turing machine with a Godel number $e$) for $n$ steps. If $\phi_e(x) \downarrow_n$ (halts after at most $n$ steps), then output $0$, otherwise output a prime number greater than $n$.

As an exercise show that $\forall e,x. \phi_e(x) \uparrow \iff M_{e,x} \in L$.

Then $\phi_e(x) \downarrow$ recognizable trivially. $\phi_e(x) \uparrow$ if $M_{e,x} \in L$, hence recognizable. Therefore the halting problem $H=\{\langle e, x \rangle | \phi_e(x) \downarrow \}$ is decidable. Contradiction.

Dávid Natingga
  • 2,889
  • 2
  • 27
  • 41
  • I think the problem is recognizable but not decidable. The problem of deciding whether or not a machine M accepts an input w is undecidable but recognizable. The proof is in Sipser's book. My thinking is, if M halts, then you can test the output and accept or reject on that basis. If M never halts, then M cannot be a decider but it is a recognizer. – user137481 Aug 05 '14 at 15:33
  • 1
    @user137481 Recognizable means that if $M \in L$ then given enough computation time you can prove it. A dual notion is if $M \not \in L$ then given enough computation time you can prove it - such a language is called co-recognizable. $L$ is co-recognizable, i.e. the complement $\bar{L}$ is recognizable. But as by my proof $L$ is not recognizable. If you are still confused, could you please include a page number reference to the proof in Sipser's book? – Dávid Natingga Aug 18 '14 at 19:39
  • You're right. A recognizer must halt and accept M if M is in L. The proof in Sipser's book refers to a different problem. I see it now that you mentioned the complement of L. It's easier for me to see that $\bar L$ is recognizable which obviously means L is not recognizable. I had some trouble with your use of Godel numbers as I haven't gotten to that part of the book yet. Anyway, thanks! – user137481 Aug 18 '14 at 21:24
  • @user137481 Beware, it is not always true that $\bar{L}$ recognizable implies $L$ not recognizable. As an example take any decidable set $A$, e.g. $\mathbb{N}$, then both $\mathbb{N}$ and $\bar{\mathbb{N}}=\emptyset$ are recognizable. My proof says that $L$ is not recognizable without any reference that $\bar{L}$ is recognizable. That was only mentioned in the comments to clarify a distinction between definitions of recognizable and co-recognizable. The intuition is that if $M \in L$ then you would need to check $M$ on infinitely many inputs in a finite time, which you cannot,hence $L$ not Re. – Dávid Natingga Aug 18 '14 at 22:10
  • It may be useful for you to prove: $L$ is recognizable iff $\bar{L}$ is co-recognizable. – Dávid Natingga Aug 18 '14 at 22:12
  • I had already proved L to be undecidable. My problem was trying to prove that L was unrecognizable. Your follow up comment broke my brain freeze. A recognizer for $\bar L$ is much more easily constructed than a recognizer for L. This is because for $\bar L$ the property is "there exists" as opposed to "for all n". Once we prove that $\bar L$ is recognizable, the fact that L is unrecognizable follows from the fact that L is undecidable. – user137481 Aug 19 '14 at 02:39
  • @user137481 You are correct. Sorry for the confusion. – Dávid Natingga Aug 19 '14 at 21:14