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.

Improve this question
$\endgroup$
2
  • $\begingroup$ What's the output of a machine that never halts? $\endgroup$
    – Steven
    Commented Feb 12, 2021 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
    Commented Feb 12, 2021 at 23:04

2 Answers 2

Reset to default
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.

Improve this answer
$\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
    Commented Feb 12, 2021 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
    Commented Feb 12, 2021 at 23:09
  • $\begingroup$ I think I got it, thank you! $\endgroup$
    – Anguepa
    Commented Feb 12, 2021 at 23:41
4
$\begingroup$

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

Improve this answer
$\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.