# Can a TM decide the binary PCP-Problem？

I am having a little bit of a hard time distinguish between a TM which accepts a language, and a $$TM$$ that decides a language. To be more precise:

$$L_1 = \{\langle M\rangle\; | \; M$$ accepts the 10-PCP $$\}$$ and $$L_2 = \{ \langle M\rangle \; | \; M$$ decides the 10-PCP $$\}$$

I guess $$L_1$$ is undecdiable, since I could potentially apply Rice's Thoerem Moreover, we know that the Problem that $$M$$ accepts $$w$$ is undecidable anyway. However, I am uncertain about $$L_2$$. For me, it seems intuitive to think that we could build a TM which rejects, if the input is a $$01$$-PCP Problem. Thus, the TM can decide it. But that seems a little bit too easy and I guess I am on the wrong trail.

The binary PCP is decidable. Let $$T^*$$ be a Turing machine that decides the language $$L_{PCP}$$ of all yes-instances to binary PCP.

We can use this fact to show that both $$L_1$$ an $$L_2$$ using a reduction from the halting problem.

Suppose towards a contradiction that there is a Turing machine $$T$$ that decides $$L_1$$ (resp. $$L_2$$). Given a Turing machine $$M'$$ we can define a new Turing machine $$M$$ that, on input $$x$$, simulates $$M'$$ on empty input and then (when/if $$M'$$ halts) simulates $$T^*$$ with input $$x$$. If/when $$T^*$$ accepts $$M$$ also accepts. If/when $$T^*$$ rejects $$M$$ also rejects.

Now, $$M^*$$ accepts (resp. decides) $$L_{PCP}$$ if and only if $$M'$$ halts on empty input. In other words $$M^*$$ belongs to $$L_1$$ (resp. $$L_2$$) if and only if $$M'$$ halts on empty input.

We can then use $$T$$ with input $$M^*$$ to decide whether $$M'$$ halts. This is a contradiction and hence no Turing machine $$T$$ exists.

• Do I understand it correctly that $L_2$ is undecdiable with your argumentation, since otherwise it would decide the halting problem? Jul 2, 2021 at 15:59
• Yes, that's correct. Jul 2, 2021 at 16:07
• One last thing, is Rice's theorem applicable to $L_1$ or $L_2$? Jul 2, 2021 at 16:13
• I think so. To both $L_1$ and $L_2$. Jul 2, 2021 at 18:59