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'

enter image description here

  • $\begingroup$ crossposted $\endgroup$ – Austin Buchanan Apr 3 '14 at 0:20
  • $\begingroup$ put a $\bar{bar}$ over it :p $\endgroup$ – vzn Apr 3 '14 at 2:16
  • $\begingroup$ seriously, you have to go back to the defn of the TM and determine what it does in each case of "palendrome detected" and "not a palendrome"... it is probably writing some particular "status" to the tape... you have to recode it to "flip" that "status"... anyway the title of the question is misleading, it cannot merely be "drawn" but needs some reconfiguration of the state table esp the next-to-end states. $\endgroup$ – vzn Apr 3 '14 at 2:18
  • 1
    $\begingroup$ Turning start states into ending states and vice versa is not how you complement a DFA. (DFAs don't even have "ending states".) DFAs are complemented by turning accepting states into non-accepting states and vice-versa. $\endgroup$ – David Richerby Apr 3 '14 at 9:13

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.

  • $\begingroup$ so you are saying that you cannot do it all by doing a complement on TM or just in this problem ? ...I know it is possible to do it in FA... $\endgroup$ – Dana Apr 3 '14 at 0:45
  • $\begingroup$ it is not so simple as "exchanging the yes and the no" or rather that hides some detail... $\endgroup$ – vzn Apr 3 '14 at 2:17
  • 1
    $\begingroup$ @Dana: FAs are not as powerful as TMs, so it's not surprising they should have other closure properties. $\endgroup$ – Raphael Apr 3 '14 at 6:36
  • $\begingroup$ @vzn Did I answer the worries you had? (ever tried to answer SE on a phone?) $\endgroup$ – babou Apr 3 '14 at 13:38
  • $\begingroup$ +8? this line does not make much sense. "Non deterministic machines do the opposite: when they say "yes" it means "yes", and when they say "no" it means "maybe". It is also "maybe" when they keep quiet (still thinking), but that is always true." $\endgroup$ – vzn Apr 3 '14 at 15:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.