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 ?
which of the following languages are Recursively Enumerable?
computability;turing machines;undecidability;semi decidability
$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 do5) 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}$.  