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.

Improve this question
$\endgroup$
6
  • 3
    $\begingroup$ Duplicate of Recursive ,recursively enumerable, see the answer there. $\endgroup$
    – Ran G.
    Commented Oct 10, 2015 at 21:44
  • $\begingroup$ @RanG. I don't think it's a duplicate please see edit. Thanks $\endgroup$
    – lapolonio
    Commented Oct 10, 2015 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.
    Commented Oct 10, 2015 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.
    Commented Oct 11, 2015 at 14:44
  • 1
    $\begingroup$ @Raphael Finally, the extended version is part of the reference question. (; $\endgroup$
    – Ran G.
    Commented Nov 14, 2015 at 19:31

1 Answer 1

Reset to default
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}$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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