# How to show that the set of TMs that accept languages of size two is recognizable?

I know how to show $\overline{Lx}$ is unrecognizable. I know how to show Lx is undecidable.

I would like the mapping reduction function that shows that Lx is recognizable or unrecognizable.

For instance, to show $\overline{Lx}$ is unrecognizable, show $\overline{Htm}$ <= $\overline{Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

def R(<M>):
def N(x):
M('')
if x == 0 or x == 1 then accept
return <N>


If M is in $\overline{Htm}$ then M loops then N will not accept any strings then |L(N)| = 0 then N is in $\overline{Lx}$

if M is not in $\overline{Htm}$ then M halts then N will accept either 0 or 1 so |L(N)| = 2 then N is not in $\overline{Lx}$

I would like a similar proof to show that Lx is either recognizable or unrecognizable.

• Duplicate of Recursive ,recursively enumerable, see the answer there. – Ran G. Oct 10 '15 at 21:44
• @RanG. I don't think it's a duplicate please see edit. Thanks – lapolonio Oct 10 '15 at 22:07
• As mentioned in the duplicate question, the extended version of Rice's theorem proves it is not RE. If you want to have a specific mapping reduction, how about doing the same reduction in your post, but always accepting $0$ and $1$, then running $M$, then accepting all other inputs. Now, if there is a loop then $|L|=2$ and otherwise it is infinite. – Ran G. Oct 10 '15 at 22:29
• @Raphael I hope to add it one day to the reference question. We should have a clear "usage" guide for Rice's thm. – Ran G. Oct 11 '15 at 14:44
• @Raphael Finally, the extended version is part of the reference question. (; – Ran G. Nov 14 '15 at 19:31

To show ${Lx}$ is unrecognizable, show $\overline{Htm}$ <= ${Lx}$

Given $\overline{Htm}$ = {M description: M is a TM and M loops on ''}

def R(<M>):
def N(x):
if x == 0 or x == 1 then accept
M('')
return accept
return <N>


If M is in $\overline{Htm}$ then M loops then N will accept either 0 or 1 then |L(N)| = 2 then N is in ${Lx}$

if M is not in $\overline{Htm}$ then M halts then N will accept all x so |L(N)| = $\infty$ then N is not in ${Lx}$