2
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ Duplicate of Recursive ,recursively enumerable, see the answer there. $\endgroup$ – Ran G. Oct 10 '15 at 21:44
  • $\begingroup$ @RanG. I don't think it's a duplicate please see edit. Thanks $\endgroup$ – lapolonio Oct 10 '15 at 22:07
  • 3
    $\begingroup$ 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. $\endgroup$ – Ran G. Oct 10 '15 at 22:29
  • 2
    $\begingroup$ @Raphael I hope to add it one day to the reference question. We should have a clear "usage" guide for Rice's thm. $\endgroup$ – Ran G. Oct 11 '15 at 14:44
  • 1
    $\begingroup$ @Raphael Finally, the extended version is part of the reference question. (; $\endgroup$ – Ran G. Nov 14 '15 at 19:31
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.