With only using our thinking. What do I have to think about when finding a complement of a Turing machine for example.

L={M∣M is a TM that halts on empty tape after even transition steps} What's the complement of L would it be:

  1. L={M∣M is a TM that does not halt on empty tape after even transition steps}
  2. L={M∣M is a TM that halts on empty tape after odd transition steps}

Please give me your train of thought when coming up with a complement for an automaton.

  • 2
    $\begingroup$ You're not being asked to find the complement of a Turing machine. You're being asked to find the complement of a language. $\endgroup$ – Tom van der Zanden Oct 3 '19 at 12:22
  • $\begingroup$ @TomvanderZanden Oh okay, I see where I made a mistake. $\endgroup$ – alexW Oct 3 '19 at 23:38

You cant find the complement of a $TM$ for undecidable languages. A decidable language is such that a $TM$ which recognizes language membership, always halts with a yes. In this case finding the complement of the machine is simple, just reverse the yes with the no, obtaining the complement of the original decision problem. I leave to you the task of determining whether the language of your example is decidable or not.

HINT: you can compare it with the Halting problem or $ATM$

| cite | improve this answer | |
  • $\begingroup$ What about a language that was co-recognizable? $\endgroup$ – Rick Decker Oct 3 '19 at 11:32
  • $\begingroup$ @RickDecker well the complement of co-recognizable is recognizable so yes, you can do it. $\endgroup$ – Yamar69 Oct 3 '19 at 12:02
  • $\begingroup$ The TM in my question is semi-decidable. When the answer is a YES (that means the machine is in L) the machine will halt but when it's a NO the machine does not halt and therefore we can't find out. However, I'm just confused how to find the complement (U - L) and U(all possible turing machines) is huge. So is compl of L option 1 or 2? or is it both? $\endgroup$ – alexW Oct 3 '19 at 23:45

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.