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?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ And what do you propose to do when $M$ runs forever on input $w$? $\endgroup$– Andrej BauerCommented Sep 2, 2017 at 16:26
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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!
-
$\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$– micszaCommented Sep 2, 2017 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$– RaphaelCommented Sep 2, 2017 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$– micszaCommented Sep 2, 2017 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$– RaphaelCommented Sep 2, 2017 at 14:23
-
1$\begingroup$ Well I was at least right in claiming it's fundamental :) Thank you $\endgroup$– micszaCommented Sep 2, 2017 at 15:30