"Reduction" from the complement of the universal language (L_u) to the language of nonempty-language Turing machines (L_ne)

Question

I have a question from the domain of theoretical computer science.

The so-called universal language, L_u, is composed of pairs (M, w) such that w \in L(M). The language L_ne consists of machines M (actually, their descriptions, but let's not be too punctilious here) with a nonempty language. We all know that both L_u and L_ne are non-recursive but still RE (recursively enumerable). On the other hand, the complement of L_u (let's call it L_nu) in not even RE, for if it were, both L_u and L_nu would have to be recursive.

If we were able to reduce L_nu to L_ne, we would prove that L_ne is non-RE, too. This implies that such a reduction should be impossible. However, I can't figure out why it should be.

First, to reduce a language L to L', we have to construct a computable function f that maps each conceivable positive instance of L to some positive instance of L' and each conceivable negative instance of L to some negative instance of L'. That's all, isn't it?

Second, I think we can safely assume that the universal Turing machine (UTM) has two final states, a YES-state and a NO-state. Of course, it can happen that if w \not\in L(M) for a given input (M, w), the UTM will never arrive to the NO-state, but we can still assume that if the UTM halts, it will do so either in the YES-state or in the NO-state. That's also correct, isn't it?

Now let's try to reduce L_nu to L_ne as follows: Given a pair (M, w), build a machine M' that runs M on w using the logic of the UTM and says NO if the UTM says YES and vice versa. Clearly, positive instances of L_nu (w \not\in L(M)) are mapped to positive instances of L_ne (L(M') is nonempty in this case, since M' always says YES), and negative instances of L_nu (w \in L(M)) are converted to negative instances of L_ne (L(M') is empty, since M' always says NO). While the machine M' clearly runs forever for at least some positive input (since there is at least one pair (M, w) with w \not\in M that makes the UTM run forever), the reduction itself is computable: the code for M' includes the code for UTM (this definitely can be done) and a simple logic that checks whether the built-in UTM, if applied to (M, w), has arrived to a YES-state or to a NO-state. That's about it.

I have thereby just "proved" that L_ne is non-RE. However, since this is not the case, I must have gone wrong somewhere. It really baffles me, since the standard reduction from L_u to L_ne, as given in, say, Hopcroft-Ullman-Motwani, employs a very similar reasoning.

If someone could help me solve this riddle, I would be grateful!

Answer 1

I have seen this question floating around and have hesitated to answer because it is pretty tricky. I have an attempted solution below where I attempt to point out what the issue might be. Please go through this carefully and see if you follow what I am trying to suggest. I believe the real crux of the issue, as I lay out in detail below, is that the UTM running M on w does not correctly handle the case where M fails to halt on w: if M fails to halt on w, then (M, w) is in L_nu, but the UTM running M on w cannot ever know that.

If we had a decider for L_ne, could we decide L_nu?

Inputs for the L_nu problem are pairs (M,w). There are three cases:

1. M enters halt-accept for input w: return no
2. M enters halt-reject for input w: return yes
3. M never halts for input w: return yes, since never halting means M does not accept w.

We can certainly compute a machine description M' which uses the UTM to run M on w and return the opposite result. There are three cases:

1. M' enters halt-accept for input w: return yes
2. M' enters halt-reject for input w: return no
3. M' never halts for input w: there is never a time we can we are stuck in a loop, so this must map to no

If we had a decider M'' for L_ne and fed M' into it, what would we get?

1. in the first case, M'' would return yes since M' accepts all inputs
2. in the second case, M'' would return no since M' accepts no inputs
3. in the third case, M'' would return no since M' accepts no inputs

In the third case, M'' - our decider for L_ne - told us no, the language L(M'') is empty. However, it does not say why the language is empty: it could be for either of the negative cases of M'. If it's because M' explicitly entered halt-reject, then we know w is in L(M), so our reduction should answer "no". If it's because M' ran forever on w, then we know M fails to halt on w, so our reduction should answer "yes".

We cannot distinguish these two scenarios when running M'', so the reduction fails. Why did it fail? It failed because M', the UTM running M on w, cannot accurately enter halt-accept in cases where M fails to halt on w. M' would never necessarily reach a point where it knew that processing would continue forever. In the general case, M' would need to run forever and in those cases, L(M') would be empty.