0
$\begingroup$

I am having hard time to proving this problem

$C=\{\langle M \rangle \mid M \text{ is a Turing Machine , } L(M) \text { only contains two different strings}\}$

some ideas that i have tried are :

  1. i have to prove if $C$ is not recursively enumerable. I know if $A$ is recursively enumerable, and $co\text{-}A$ is recursively enumerable, then $A$ is recursive. so the first idea is proving if $co\text{-}C$ is recursively enumerable, but i stuck in how to find $u$ and $v$ so that $co\text{-}C$ will not accept.

  2. as co-halting problem is not recursively enumerable, i think $C$ can be reducible from co-halting problem. then if TM $M$ that recognizes $C$ can be use to solve co-halting problem that it proves the problem, but i don't really understand how exactly to prove it.

  3. the idea is the same with #2, but using $A_{TM}$.

Can anyone give me some explanation this problem, or what the best way to prove the problem.

thank you a lot. EDIT : the problem is how to prove $C$ is not recursively enumerable

$\endgroup$

migrated from stackoverflow.com Nov 11 '17 at 17:58

This question came from our site for professional and enthusiast programmers.

  • 1
    $\begingroup$ Your "problem" is a set of machines; what exactly are you trying to prove? $\endgroup$ – Scott Hunter Nov 5 '17 at 0:18
  • $\begingroup$ oh, i'm sorry, the problem is how to prove that C is not r.e as i edited the question. thanks $\endgroup$ – paiman Nov 5 '17 at 1:30
  • $\begingroup$ This seems relevant: math.stackexchange.com/a/38018 $\endgroup$ – Scott Hunter Nov 7 '17 at 18:32
  • 2
    $\begingroup$ Hint: Prove that co-C is r.e. ( run M on input 1,2,3,... and as soon has it accepts more than ...); then apply Rice ... $\endgroup$ – Vor Nov 11 '17 at 19:41

Your Answer

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