1
$\begingroup$

I know $USELESS_{TM}$ is undecidable, but am having trouble showing that it is recursively enumerable. I wanted to reduce $USELESS_{TM}$ to the halting problem, which would show that $USELESS_{TM}$ is recursively enumerable but don't see a way to go about doing this. (I think I would need to check every possible input to see if a state is not entered which I don't know how to simulate using a halting problem subroutine.)

$\endgroup$
  • $\begingroup$ what's a useless state? $\endgroup$ – jkabrg Nov 21 '17 at 16:57
  • $\begingroup$ A state is useless if it is never entered on any input. $\endgroup$ – user79943 Nov 21 '17 at 17:07
1
$\begingroup$

The reason you are struggling to reduce USELESS to the Halting problem might be that it is not recursively enumerable after all. Since you already have a proof of undecidability, it is enough to see that USELESS is co-ce:

Given some TM M, we enumerate all its states as $s_1$ ... $s_n$. We can search through potential inputs $w_0,w_1,\ldots$ and mark each state that one of the computation visits. If we ever mark all states, we halt. This gives a procedure that recognizes exactly the complement of USELESS.

$\endgroup$
  • $\begingroup$ Thank you for clarifying! No wonder I was having so much trouble... co-ce means not recursively enumerable right? $\endgroup$ – user79943 Nov 21 '17 at 17:29
  • 1
    $\begingroup$ co-ce means that the complement of the language is recursively enumerable (=ce). If a language is both ce and co-ce, then it is decidable. So an undecidable language can be at most one out of c.e. and co-c.e. $\endgroup$ – Arno Nov 21 '17 at 18:08
0
$\begingroup$

Have you used Rice theorem to show that's it's undecidable ? If so, it also shows that the problem can be transformed to the halting problem, because the proof of Rice theorem contains that transformation. You can easily find that proof and see how the transformation is accomplished.

But, are you sure that reducing your set to the halting problem shows that it's recursively enumerable ?

$\endgroup$
  • $\begingroup$ Rice' theorem does not apply here. $\endgroup$ – Arno Nov 21 '17 at 17:16
  • $\begingroup$ Why doesn't it ? $\endgroup$ – user80502 Nov 21 '17 at 17:21
  • $\begingroup$ Because the property we are dealing with does not just depend on the function computed by the TM, but on the specific implementation. $\endgroup$ – Arno Nov 21 '17 at 17:22
  • $\begingroup$ Yes, you are right. Haven't noticed that. $\endgroup$ – user80502 Nov 21 '17 at 17:26

Your Answer

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