# 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.

• 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. – Yonatan N Sep 6 '19 at 8:40

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.