2
$\begingroup$

In the book Introduction to Automata Theory there is a question 9.3.4 that asks if a question "whether a language L(M) is infinite" is RE or non-RE? I've seen the answer, that its non-RE, however I tried a reduction from a Universal Turing machine language(which is RE) and it also seemed to work. Since a language can't be both RE and non- RE, there is a mistake and I can't figure out where. Please help!

My reduction from Lu (univeral TM) to Lm (infinite language TM): The input to Lu is (M,w). Build a new TM M' with an input x as follows, let it simulate a string w on M and if it accepts, then M' goes to states where it accepts a language 0^n, n>1, and accept its input x. If M rejects w or doesn't halt, then M' never accepts its input x. Then take the description of this machine M' and feed it into Lm. Therefore, if M accepts w, M' accepts an infinite language and Lm accepts it. If M doesnt accept w, then M' only accepts ∅ language, which is finite, hence Lm rejects.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Reducing A to B shows that B, in an appropriate sense, captures all the complexity of A. So your reduction shows that solving the infinite-language problem is at least as hard as simulating a Turing machine. But that's not what you need to prove to show that a problem is RE. You need to reduce Lm to Lu, which shows that the infinite-language problem can be appropriately captured by a universal Turing machine. $\endgroup$
    – Yonatan N
    Commented Sep 6, 2019 at 8:40
  • $\begingroup$ Much simpler construction: Disregard the input, just accept if $M$ accepcts $w$. In that case it accepts $\varnothing$ (a finite language) or anything at all (an infinite languiage) $\endgroup$
    – vonbrand
    Commented Jul 2, 2022 at 17:51

1 Answer 1

Reset to default
1
$\begingroup$

Your reduction actually shows that $L_m$ is not co-RE. Indeed, if $L_m$ were co-RE, then your reduction shows that $L_u$ is also co-RE. However, $L_u$ is known to be RE but not recursive, hence cannot be co-RE.

Similarly, you can show that $L_m$ is not RE, by reduction from the complement of the halting problem: given an instance $(M,w)$ of $L_u$, create a new machine $M'$ which on input $n$ simulates $M$ on $w$ for $n$ steps. If $M$ halts, $M'$ gets into an infinite loop, and otherwise it halts. You can check that $M$ halts on $w$ iff $L(M')$ is finite.

The language $L_m$, usually known as INF, is actually one of the canonical examples of $\Pi_2$-complete languages, making it harder than the halting problem.

Your title suggests that you believe that RE languages cannot be reduced to non-RE languages. But in fact, every recursive language can be reduced to every non-RE language. I'll let you work this out.

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.