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


suppose there deterministic turing machine, e.g. 1 runs in polynomial time, , decides language l.

does automatically means decides l's complement language?

when saying l's complement language, of course mean language k, such that:

k = {x : x not in l}

suppose have deterministic turing machine bounded running time, can build turing machine accepts complement of l reversing answer. however, requires turing machine stop on every input (which case if decides language l , stops on every input). machine not decider complement of l, because decider of language has accept it.

in general case machine merely accepts (only has stop on inputs "yes"-answers) not decides (stops on every input) language l endless loop inputs not in l, therefore there possibly no explicit "no"-answer reversed.


Comments

Popular posts from this blog

Android : Making Listview full screen -

javascript - Parse JSON from the body of the POST -

javascript - Chrome Extension: Interacting with iframe embedded within popup -