Search code examples
complexity-theorycomputation-theoryturing-machines

If a deterministic Turing Machine decides a language L, does it mean that it also decides L's complement?


Suppose that there is a deterministic Turing Machine, e.g. one that runs in polynomial time, and decides a language L.

Does it automatically means that it also decides L's complement language?

When saying L's complement language, I of course mean to a language K, such that:

K = {x : x not in L}


Solution

  • Suppose you have a deterministic Turing machine with a bounded running time, you can easily build a Turing machine that accepts the complement of L by reversing its answer. However, this requires the Turing machine to stop on every input (which is the case if it decides the language L and thus stops on every input). The machine itself is not a decider for the complement of L, because a decider of a language has to accept it.

    In the general case a machine that merely accepts (only has to stop on inputs with "yes"-answers) but not decides (stops on every input) the language L could get into an endless loop for inputs that are not in L, therefore there is possibly no explicit "no"-answer that could be reversed.