HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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

Submitted by: @import:stackexchange-cs··
0
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!

Context

StackExchange Computer Science Q#80759, answer score: 3

Revisions (0)

No revisions yet.