1
$\begingroup$

The question itself:

Let $f:\mathbb{N}\to\Sigma^\star$ be such that $f(n)$ returns the $n$-th word in $\overline{H_{TM,\epsilon}}$ (which is the complement of the language of TMs which accept $\epsilon$, i.e. the TMs which reject or do not halt on $\epsilon$). Prove/disprove: $f$ is computable.

My approach:

I started to disprove this one by contradiction. I know that $H_{TM,\epsilon}\in \mathcal{RE}\setminus\mathcal{R}$ and thus, $H_{TM,\epsilon}\not\in co-\mathcal{RE} $, so $\overline{H_{TM,\epsilon}}\not\in\mathcal{RE}$. Then we get that there is no TM $M$ such that $L(M)=\overline{H_{TM,\epsilon}}$ but if $f$ is computable we can contruct a TM which accepts $\overline{H_{TM,\epsilon}}$:

The TM on input $\langle M\rangle$ (encoding of a valid TM) will run $f(n)$ for $n=1$ and on and if $f(n)=\langle M\rangle$ it will accept otherwise continue.

Then if $\langle M\rangle\in\overline{H_{TM,\epsilon}}$ there exists some n such that $f(n)=\langle M\rangle$ otherwise the new TM will not halt. So we contructed a TM for a language that is not recursively enumerable, contradiction.

Please tell me if my approach is good and if not help me understand my mistake and get to the right answer.

$\endgroup$
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael May 23 '16 at 22:15
  • $\begingroup$ That said, your idea is good. You'll need to elaborate until you get a formal proof, though. $\endgroup$ – Raphael May 23 '16 at 22:16
  • 1
    $\begingroup$ The title you have chosen is not well suited to representing your question. Please take some time to improve it; we have collected some advice here. Thank you! $\endgroup$ – Raphael May 23 '16 at 22:17
  • $\begingroup$ Yes, the key here is to realize that the question is "Is there a computable enumerator for a language that is not recursively enumerable"? $\endgroup$ – Raphael May 24 '16 at 9:07

Your Answer

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

Browse other questions tagged or ask your own question.