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?


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 Sep 30 '18 at 5:28
  • $\begingroup$ Then, computer science has more insights into many other computational problems. $\endgroup$ – Thinh D. Nguyen Sep 30 '18 at 11:36
  • $\begingroup$ But can we resolve the P vs NP problem assuming it? $\endgroup$ – user93928 Sep 30 '18 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy