On-line simulation of k + 1 tapes by k tapes requires nonlinear time

Abstract

On-line simulation of real-time (k + 1)-tape Turing machines by k-tape Turing machines requires time n(log n)1/(k+1). © 1982 Academic Press, Inc.