Cheap and Secure Web Hosting Provider : See Now

[Answers] How to show that the set of TMs that accept languages of size two is recognizable?

, , No Comments
Problem Detail: 

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.

Asked By : lapolonio

Answered By : lapolonio

Based on RanG. answer in comments.

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}$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48094

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback