Question

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 ?

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top