# Turing machine that checks whether a given string is an output of a given machine and input

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.

• What's the output of a machine that never halts? Commented Feb 12, 2021 at 21:56
• 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. Commented Feb 12, 2021 at 23:04

## 2 Answers

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.

• I'm afraid I'm a mathematician that knows very little about computability. What exactly does it mean that it "simulates" M? Commented Feb 12, 2021 at 23:02
• $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. Commented Feb 12, 2021 at 23:09
• I think I got it, thank you! Commented Feb 12, 2021 at 23:41

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