3
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ And what do you propose to do when $M$ runs forever on input $w$? $\endgroup$ – Andrej Bauer Sep 2 '17 at 16:26
3
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – micsza Sep 2 '17 at 9:55
  • $\begingroup$ @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. $\endgroup$ – Raphael Sep 2 '17 at 10:52
  • $\begingroup$ 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? $\endgroup$ – micsza Sep 2 '17 at 14:08
  • $\begingroup$ @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. $\endgroup$ – Raphael Sep 2 '17 at 14:23
  • 1
    $\begingroup$ Well I was at least right in claiming it's fundamental :) Thank you $\endgroup$ – micsza Sep 2 '17 at 15:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.