1
$\begingroup$

Is there a Turing machine such that, given a description $\langle M \rangle$ of a Turing machine $M$, an input $x$ and a string $y$, computes whether or not $y$ is the output of $M$ input $x$?

My guess is that the answer is no because this might imply that the set of strings with Kolmogorov complexity greater than or equal to their length is decidable.

$\endgroup$
2
  • $\begingroup$ What's the output of a machine that never halts? $\endgroup$
    – Steven
    Feb 12 at 21:56
  • $\begingroup$ If M input x does not halt then for any y the machine would answer that y is not an output of M input x. $\endgroup$
    – Anguepa
    Feb 12 at 23:04
3
$\begingroup$

No. Any such machine $T^*$ would allow you to immediately solve the halting problem. Given a description of $M$, construct a Turing machine $T_M$ that simulates $M$ and then outputs some fixed string, e.g., "0". Notice that, given $M$, $T_M$ is computable.

Then $T^*$ with input $T_M$ and "0" accepts if $M$ halts and rejects if $M$ does not halt.

$\endgroup$
3
  • $\begingroup$ I'm afraid I'm a mathematician that knows very little about computability. What exactly does it mean that it "simulates" M? $\endgroup$
    – Anguepa
    Feb 12 at 23:02
  • $\begingroup$ $T_M$ is just a Turing machine that behaves exactly like $M$ until $M$ returns, and then does some more things (i.e., it erases the tape and writes a single "0"). A description of $T_M$ can be derived from a description for $M$. Alternatively, a $T_M$ can "execute" (simulate) $M$ directly from its description. See Universal Turing Machine for the details. $\endgroup$
    – Steven
    Feb 12 at 23:09
  • $\begingroup$ I think I got it, thank you! $\endgroup$
    – Anguepa
    Feb 12 at 23:41
4
$\begingroup$

No, in fact any non-trivial semantic property of Turing machines is undecidable. This result is Rice's theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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