2
$\begingroup$

I want to show that the language $$L= \left\{ \left\langle M\right\rangle \mid\substack{\text{M is a TM and there exists a poly TM $M'$ such that}\\ \text{if M halts on input $w$, $M'$ halts on $w$ and answers the same} } \right\} $$ is not decideable, using Rice's theorem.

I have a hard time understanding why this property is semantic. I obviously can't assume that $M \in R$ , so it might be that we have TMs $M_{1},M_{2}$ such that $L(M_{1})=L(M_{2})$, but $M_{1}$ gets stuck on some input $z$, while $M_{2}$ rejects it. Then, the property above (having a poly TM which identifies with $M$ on inputs which it halts on) might possibly apply for $M_{1}$ but not for $M_{2}$ (as $M_{1}^{\prime}$ doesn't have to satisfy anything about $z$, while $M_{2}^{\prime}$ must reject it). But according to the exercise I have to use Rice's theorem, so I am probably missing something and this property is semantic after all.

I saw this related question but it didn't really help.

$\endgroup$
17
  • $\begingroup$ The condition only depends on $L(M)$, that is, it is semantic. $\endgroup$ Commented Jun 28, 2022 at 18:54
  • 1
    $\begingroup$ If you think of $L(M)$ as a partial function from $\Sigma^*$ to $\Sigma^*$, then the problem disappears. $\endgroup$ Commented Jun 28, 2022 at 19:07
  • 1
    $\begingroup$ You have to define $L(M)$ accordingly. The upshot is that whether $\langle M \rangle$ is in the language or not depends only on what $M$ computes, not on how it computes it. We only care, for each input $x$, whether $M$ halts on $x$, and if so, what does it output. We don't care about anything beyond that. $\endgroup$ Commented Jun 28, 2022 at 19:13
  • 1
    $\begingroup$ Repeating, you have to define $L(M)$ as specifying, for each $x$, whether $M$ halts on $x$, and if so, the output. This is the semantic description of the partial function computed by $M$, and it suffices in order to decide membership in your language. $\endgroup$ Commented Jun 28, 2022 at 19:27
  • 1
    $\begingroup$ Right, that makes more sense in this application. In other applications we might not allow different types of final states, but we might be interested in the output of the machine. It all depends on the exact model of Turing machine that we're using. $\endgroup$ Commented Jun 28, 2022 at 19:47

1 Answer 1

1
$\begingroup$

Informally speaking, a property is semantic if it only depends on the final "outcome" of running $M$ on a given input rather than on the workings of $M$. In order to formalize this, with each Turing machine $M$, associate a partial function $\Lambda$ from inputs $\Sigma^*$ to pairs $\{0,1\} \times \Sigma^*$, where the first element denotes whether the final state accepts and rejects, and the second element denotes the output of the machine (the contents of the tape). This is a partial function, since if $M$ doesn't halt on an input $x$, then $\Lambda(x)$ is undefined.

Suppose that $P$ is a nontrivial property of partial functions $\Lambda$ of that form. Nontriviality means that there exists some Turing machine $M_+$ such that $\Lambda(M_+) \in P$, and there exists another Turing machine $M_-$ such that $\Lambda(M_-) \notin P$.

If $P$ is decidable then consider the Turing machine $Q$ which on input $x$, determines whether $\Lambda(Q) \in P$ (this self-reference can be implemented using the recursion theorem), if so runs $M_-$ on $x$, and otherwise runs $M_+$ on $x$. By construction, if $\Lambda(Q) \in P$ then $\Lambda(Q) = \Lambda(M_-) \notin P$, and if $\Lambda(Q) \notin P$ then $\Lambda(Q) = \Lambda(M_+) \in P$. In both cases we obtain a contradiction.

Crucially, the identities $\Lambda(Q) = \Lambda(M_\pm)$ implicitly rely on the fact that $\Lambda$ only captures semantic properties. The syntactic properties could well be different, since $Q$ isn't the same as $M_\pm$, it just simulates those machines.

$\endgroup$

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.