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
$\begingroup$
$\endgroup$
3
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.
answered Sep 30, 2018 at 2:56
-
$\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$– user93928Sep 30, 2018 at 5:28
-
$\begingroup$ Then, computer science has more insights into many other computational problems. $\endgroup$ Sep 30, 2018 at 11:36
-
$\begingroup$ But can we resolve the P vs NP problem assuming it? $\endgroup$– user93928Sep 30, 2018 at 12:12