I want to know if anybody knows a detailed proof of Theorem 2.1 of Papadimitrou's book Computational Complexity. The theorem states "Given any $k$-string Turing machine $M$ operating within time $O(f(n))$, we can construct a Turing Machine $M'$ operating within time $O(f(n)^2)$ and such that, for any input x, $M(x)=M'(x)$."

When asking for a detailed proof, I am asking for a complete description of $M'$. For instance, in the proof of the book, there are statements (paragraph 4), like: "$M'$ must contain new states, each of which corresponds to a particular combination of a state of $M$ and of a $k$-tuple of symbols of $M$.", which are not detailed.

Do not misunderstand me, I do understand the proof, so I am not asking for an explanation. I want to know if anybody (maybe an old paper) make the effort to write a complete configuration for the new machine.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.