This is actually an old exam question its not my homework;
Let L = { : M is a TM with an input alphabet of {a,b} and M accepts at most one word, i.e. M either accepts no words or accepts exactly one word}. Prove that the complement of L is
Turing-recognizable.
I know the definition of Turing recognizable but when it comes to make an example it is really difficult for me. In Sipser's book he only proof that ATM is Turing recognizable but it is kind of abstract for me.
What I have done for this question is (I am not sure at all)
I tried to show that this language is decidable in that way complement of this language will be Turing recognizable.
T= On input where M is a TM
1.) Construct a DFA O that accepts one word (edit)
2.) Construct a DFA C that accepts no words (edit)
3.) Construct a DFA B such that L(B)= L(M) ∩ ( L(O)∪ L(C) ) (Edit)
4.) Test whether L(B)={empty set} using EDFA decider E
5.) If E accepts reject, rejects accept. (edit)
This is what I have done.
Questions
1.)What should I really do to prove T.R (please make an example not a definition)
2.)Can you help me to write complement of this L and prove that it is T.R or not
3.)or can you verify my answer
Regards,
Best Answer
Since $L$ is not computable, there is no way you are going to be able to proceed by trying to decide it. You need to work directly with the complement of $L$. Depending on your encoding, the complement of $L$ will either be exactly the codes for those Turing machines with alphabet $\{a,b\}$ which accept at least two words, or it may also contain some invalid codes as well (which are easily identifiable). So the problem essentially comes to recognizing those Turing machines with alphabet $\{a,b\}$ which accept at least two words. I will assume the former case for simplicity: so the complement of $L$ is the set of codes for Turing machines which accept at least two strings.
One can recognize this language using a standard technique called dovetailing. Given code for a Turing machine $M$, use a universal Turing machine to simulate steps in the computations $M(\lambda)$, $M(a)$, $M(b)$, $M(ab)$, etc., so that over time you simulate all computations of $M$ on all possible input strings. For instance, you may first simulate $M(\epsilon)$ for $1$ step, then $M(\epsilon)$ and $M(a)$ for two steps each, then $M(\epsilon)$, $M(a)$, and $M(b)$ for three steps each, and so on, so that for any string $\sigma$ and number of steps $n$, you eventually will simulate $M(\sigma)$ for $n$ steps. Thus, if $M$ accepts a string $\sigma$, you will eventually discover this by simulating enough steps for $M(\sigma)$ to halt and accept. Thus, you can halt and accept if you ever see $M$ accept on two different strings during the course of this simulation. You will halt and accept for any $M$ which accepts at least two strings, while you will never halt otherwise. This procedure therefore recognizes the set in question.