Is the set of instances of PCP, which have a solution, semi-decidable?

Question

My idea was that it is because we can construct a TM M' that simulates a TM M that is to find a solution for a PCP instance. M' accepts if M accepts, rejects if M rejects, and doesn't halt if M does not.

But I'm confused about the fact that in such a way we can also construct a TM M'' that simulates M. It rejects if M accepts and accepts if M rejects => the set of PCP instances that have no solution is semi-decidable.

The second set is a complement of the first one and they're both semi-decidable, which means that they're also decidable, so we can say when an instance has a solution (which is not the case, right?).

What am I missing?

Massive thanks for your explanations!

Answer 1

You are essentially reasoning on the language $A_{TM}$ rather than on $PCP$ instances. An algorithm such as the one you mention will show that $A_{TM}$ (i.e. the language of pairs of Turing machines a words such that the Turing machine accepts the word) is a semi-decidable language. Now, the complement of $A_{TM}$ is not even semidecidable. This is because this language consists of all pairs of Turing machines and words such that the Turing machine does not accept the word. In particular, this language contains those words for which the Turing machine does not halt, and you know that halting is undecidable. So I think in your reasoning above you were essentially missing the part on the negation of accepting being either rejecting or terminating.