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.
    Oct 10, 2015 at 21:44
  • $\begingroup$ @RanG. I don't think it's a duplicate please see edit. Thanks $\endgroup$
    – lapolonio
    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.
    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.
    Oct 11, 2015 at 14:44
  • 1
    $\begingroup$ @Raphael Finally, the extended version is part of the reference question. (; $\endgroup$
    – Ran G.
    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 that you have read and understand our privacy policy and code of conduct.

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