# Construction of the complement of universal Turing machine - where is the catch?

This is pretty fundamental but I'm getting confused. Let $U$ be the Universal Turing Machine and $L_{u}$ the language it accepts which is recursively enumerable. Obviously we are not able to construct the machine for its complement i.e. for $\bar{L_{u}}$, otherwise the whole theory crashes but still let's try. Let $V$ be a Turing Machine constructed the same way as $U$ but with the final states switched i.e.: on input code $\langle M, w \rangle$ it simulates $M$ on $w$ but if $M$ accepts $w$ then $V$ rejects $\langle M, w \rangle$ and if $M$ rejects $w$ then $V$ accepts $\langle M, w \rangle$ (implicitly if $M$ loops then $V$ loops). So the language that $V$ accepts is $\bar{L_{u}}$, isn't it? There must be a flaw in this construction but where?

• And what do you propose to do when $M$ runs forever on input $w$? Sep 2 '17 at 16:26

Let V be a Turing Machine constructed the same way as U but with the final states switched

This construction won't work. This is a pattern in automata theory, by the way: for deterministic deciders, flipping final states provides a new proof for closure against complement. For all others, it usually fails.

Here, observe that your semi-decider $U$ of L is, by definition, of the form:

Accept after finite time if $w \in L$; loop otherwise.

With your construction for $V$, you get:

Reject after finite time if $w \in L$; loop otherwise.

This is not a semi-decider for $\overline{L}$!

Intuitively, you can not flip a non-termination; you don't get the result you would flip!

• I suspect I'm missing some fundamental point here but I don't know yet which one ... Is $V$ a legal Turing machine? If so what is the language it accepts? Sep 2 '17 at 9:55
• @micsza It sure is a legal Turing machine, but it's not a language acceptor. That's the point! Flipping the answer of a decider gives you a decider, but flipping the answer of an acceptor gives you something that is not an acceptor.
– Raphael
Sep 2 '17 at 10:52
• Ok, I think I'm getting the point where I'm wrong with my thinking: $\bar{L}_{u}$ is the set of $\langle M,w \rangle$ such that $M$ does not accept $w$ and this is equal to either $M$ rejects $w$ or $M$ loops for $w$, while $L(V)$ is just the first of it ... so I wrongly substituted "rejects" = "not accepts". Is that correct? Sep 2 '17 at 14:08
• @micsza It seems indeed you have to go back over the definitions. You write: "Let U be the Universal Turing Machine and $L_u$ the language it accepts" -- then $L_u = \{ w \mid U(w) \text{ accepts}\}$. The complement of $L_u$ is well-defined without refering to $U$, namely: $\overline{L_u} = \Sigma^* \setminus L_u$. Which can of course be written as $\overline{L_u} = \{ w \mid U(w) \text{ does not accept}\}$. "Not accepting" can be "reject" or "loop" -- and yes, missing that was your problem.
– Raphael
Sep 2 '17 at 14:23
• Well I was at least right in claiming it's fundamental :) Thank you Sep 2 '17 at 15:30