which of the following languages are Recursively Enumerable?
-
04-11-2019 - |
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