patternMinor
Construction of the complement of universal Turing machine - where is the catch?
Viewed 0 times
theuniversalconstructionwherecatchmachinecomplementturing
Problem
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?
Solution
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!
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!
Context
StackExchange Computer Science Q#80759, answer score: 3
Revisions (0)
No revisions yet.