Can't find a mistake in reduction from RE language to a non-RE language 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.
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.