0
$\begingroup$

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.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.