# 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? – Steven Feb 12 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. – Anguepa Feb 12 at 23:04

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.
• $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. – Steven Feb 12 at 23:09