how to draw a complement of a Turing Machine?

Problem Detail: 

I am now pretty confident on how I would turn something into a Turing Machine. Now my question is how do you convert TM into a complement of a Turing Machine. From what I can remember in Finite Automata, complementing it you would just turn a start state into a ending state, also if you have an ending state you would make it into a start state..How would you do complement of a Turing Machine ?

For example here I have a simple TM of a Palindrome and I want a Palindrome'

Asked By : Dana

Answered By : babou

You cannot do it in general.

It would make the complement of your language semi-decidable, like the language itself. Hence they would be both decidable by running both machines in parallel.

Of course, this concerns only the case of semi -decidable languages for which the TM does not always halt for words not in the language.

If you have a decidable language for which the TM always halt with a yes or a no, you just exchange the yes and the no.

However there are some precautions to be taken:

• compatibility of accepting and non-accepting configurations

  Depending on your chosen definition of Turing Machines, accepting and halting non-accepting configurations may not be compatible, hence may not be interchangeable. If it is allowed for an accepting state to have transitions that could be used, then making it a normal state may just make the computation go on, rather than halt without accepting. Hence some rather simple precautions must be taken regarding how acceptance and rejection are identified and how to exchange them.

• non-deterministic machines

  Non deterministic machines are anti-managers. When a manager says "no" it means no, and when he says "yes" it means "maybe".

  Non deterministic machines do the opposite: when they say "yes" it means "yes", and when they seem to say "no" (halting in a non-accepting configuration) it means "maybe". The reason it means maybe is that it might have answered yes with a different non-deterministic choice of some transitions. Actually, non-deterministic automata should be more accurately supposed never to give a negative answer. It is convenient with deterministic automata, but means nothing with non-deterministic ones. It is also "maybe" when they do not terminate, for two reasons: (1) another transition choice might have produced acceptance, and (2) you cannot assert non acceptance as the computation may go on.

  Hence it is not easy to complement a language recognized by a non-deterministic or non halting device. You cannot simply exchange "yes" and "no", since you only have "yes" and "maybe". You would only get a managerial machine answering only "no" or "maybe", not recognized by the Automata Theory Union. Automata must accept by terminating and answering "yes" unambiguously iff the word to be recognized is in the language. Being able to answer no in some cases is just a bonus of deterministic machines, when kind enough to halt.

  So, you must first convert your machine into a deterministic one. Then you can exchange accepting and rejecting configurations (with due respect to the previous point above), assuming furthermore that the machine always halt.

  To get the complement of a regular set, it is convenient to first buid a DFA that recognizes it.

  A Turing machine can always be turned into a deterministic one, but it may not halt, thus leaving room for "maybe". Hence it is not always possible to complement a language recognized by a Turing Machine, as stated above. But it is possible for a (determinized) TM that always halt with a yes/no answer.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/23375