Recently, I've read Hennie's Paper. I understood the construction of buffer zones, but why can't it be applied to yield a single-taped Turing machine?


1 Answer 1


Just because that UTM itself requires $2$ tapes to do its task that efficient. Removing one tape, the magic is gone.

But assuming you have the fantasy power to do efficient $1$-tape simulation, what gains do we have then?

That should be the question rather than your question.

  • $\begingroup$ If an efficient 1-tape simulation is possible, then the problem of verifying palindromes can be done in O(nlogn) time, which is impossible, right? $\endgroup$
    – user93928
    Commented Sep 30, 2018 at 5:28
  • $\begingroup$ Then, computer science has more insights into many other computational problems. $\endgroup$ Commented Sep 30, 2018 at 11:36
  • $\begingroup$ But can we resolve the P vs NP problem assuming it? $\endgroup$
    – user93928
    Commented Sep 30, 2018 at 12:12

Your Answer

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