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, privacy policy and cookie policy

Browse other questions tagged or ask your own question.