Undecidable language and Turing Machines

Question

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?

Answer 1

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$?

Answer 2

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}$.