1
$\begingroup$

I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about.

If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine that recognizes the complement of A?

To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine. Also seeing as the Language is undecidable, this Turing Machine will not halt for strings that are not in the language.

Can someone please tell me if my understanding is correct or not, and if not give me some clarification?

|cite|improve this question
$\endgroup$
  • $\begingroup$ If it's Turing-Recognizable (a.k.a. semidecidable) but undecidable, its complement will necessarily be unsemidecidable. (To see this, consider that if you semidecided both $A$ and its complement, you could decide $A$.) $\endgroup$ – PyRulez Jan 17 '16 at 15:43
1
$\begingroup$

To my understanding this turing machines accept states, are all those that were of the rejection states in the first Turing Machine.

You presume to know something about how the machine for $\overline{A}$ was built; don't, because you can't.

What's more, this construction (flipping accepting states) does not work for TMs that do not always halt, as any one for $A$ has to be.

Thus, a semi-decider for $\overline{A}$ has to look differently from what you describe.

Regarding the original problem you were given, it is a weird formulation to test your understanding of basic closure properties.

Hint: Assume there was a semi-decider for $\overline{A}$. What follows about $A$?

|cite|improve this answer
$\endgroup$
1
$\begingroup$

You can conclude that it doesn't exist. If $L$ is recursively emumerable, but not recursive, then $\overline{L}$ is not recursive enumerable, i.e., there is no Turing machine that accepts $\overline{L}$.

|cite|improve this answer
$\endgroup$

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.