1
$\begingroup$

Which of the following languages are recursively enumerable?

A={⟨M⟩∣ TM M accepts at most 2 distinct inputs}

B={⟨M⟩∣ TM M accepts more than 2 distinct inputs}

For first language I think that we can enumerate all the TM's which accept at most 2 distinct inputs using dovetailing method and same is the case with B language.

But on the contrary, both languages are complement of each other so if one is R.E then other one cannot be. So I know that I am going wrong somewhere.

Can someone please explain me how to find if these languages are R.E ?

$\endgroup$
  • $\begingroup$ How do you enumerate all TMs which accept at most two distinct outputs? How do you know that a TM doesn't accept all outputs are than two given ones? $\endgroup$ – Yuval Filmus Jun 16 '17 at 23:27
2
$\begingroup$

$B$ is r.e, but $A$ is not.

You can construct a TM which takes as input $M$ and simulates $M$ on every string of $0$ and $1$ in canonical order for each step $n$. In other words, if $s_1, s_2,...$ are strings on $0$ and $1$ in canonical order, then starting from $n=0$ you run $M$ for $n$ steps on $s_1, s_2,..., s_n$, that is, for each $n$ run $M$ on all $s_1, s_2,..., s_n$ for $n$ steps (not just 1 step for $s_1$, 2 steps on $s_2$,... careful!). Each time just check if a string is accepted. If more than two strings are accepted then halt with accept, otherwise go on.

However we cannot use the same approach for $A$ since we cannot check infinitely many strings and say that they are not accepted except 1 or 2 certain strings IN FINITE amount of time. In other words, suppose we somehow determined that $M$ has accepted two strings, then how can we decide that the rest of infinite number of strings are not accepted by $M$ in finite amount of time?

You can also use the Rice's theorem for recursive index set. $A$ violates the containment property in the Rice's theorem. Namely, if $L$ is in $A$ and $L \subseteq L'$ for some r.e. $L'$, then $L'$ is in $A$. Assume $L=\{00, 11\}$. Then $L$ is in $A$. Let $L'=\{00,11, 01, 10\}$. Then $L \subseteq L'$ where $L'$ is clearly r.e. But $L' \notin A$.

Update (upon comment)

Task: We want to systematically simulate each TM on every input on $\{0, 1\}$.

Solution: First note that there is a one-to-one correspondence $f$ between the set of natural numbers $N$ and $N^3$ all 3-tuples of natural numbers. So, we can effectively convert each integer $m$ into the corresponding 3-tuple $<i,j,k>$. This means that if we start to count all integers then we can enumerate all possible 3-tuples, so that each 3-tuple is eventually reachable in a finite amount of time.

Now, assume we we have fixed enumerations of all TMs and strings on $0$ and $1$, e.g., $M_i$'s and $s_j$'s.

1) Set $n =0$

2) $<i, j, k> = f(n)$ <= compute 3 tuple

3) Simulate the Turing machine $M_i$ on input $s_j$ for $k$ steps.

4) If $M_i(s_j)$ halts (after $k$ steps) then do whatever you want to do

5) increase $n$ by 1 and go to step 2)

Thus, every machine "has a chance" to run on every input for arbitrary number of steps, fair isn't it?

If some machine, say, $M_{332}$ halts on input $s_{12}$ then there is an integer, say, $461$, so that $M_{332}(s_{12})$ halts in 461 steps. So, if for example $55993$ corresponds to the 3-tuple $<332, 12, 461>$, then when $n$ reaches $55993$ (in the algorithm above) you detect that $M_{332}$ halts on input $s_{12}$.

$\endgroup$
  • $\begingroup$ Thanks for your answer. I understood your explanation. I have just one doubt about dovetailing . In dovetailing, as per my knowledge we execute the TM's in interleaved manner. My doubt is whether we also run the inputs for each TM in an interleaved manner? $\endgroup$ – Zephyr Jun 17 '17 at 5:18
  • $\begingroup$ I didn't use dovetailing in my proof. I simulate a single machine systematically on all inputs until two strings are accepted. As for dovetailing, AFAK we systematically (in breadth-first-search manner) simulate every machine on a single input or many inputs depending on your task. $\endgroup$ – fade2black Jun 17 '17 at 8:50
  • $\begingroup$ Suppose we use dovetailing and run a single input on multiple TM's in an interleaved manner. If one TM goes into infinite loop because of that input then it will not be able to accept other inputs further. How will you handle that? $\endgroup$ – Zephyr Jun 17 '17 at 10:55
  • $\begingroup$ We do not simulate TMs on a certain input until it accepts or rejects. We simulate "step-by-step". Please see updates in my post. $\endgroup$ – fade2black Jun 17 '17 at 11:34
  • $\begingroup$ Doesn't "rejects" and "does not accept" mean the same thing? 2. and 3. are the same language. The first language is complement of the 2. They are all r.e. languages. In fact, they are more than r.e., they are recursive (or decidable) languages. $\endgroup$ – fade2black Jun 17 '17 at 14:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.