It has long been known that increasing the number of tapes used by a Turing machine does not provide the ability to compute any new functions. On the other hand, the use of extra tapes does make it possible to speed up the computation of certain functions. It is known that a square factor is sometimes required for a one-tape machine to behave as a two-tape machine and that a square factor is always sufficient. The purpose of this paper is to show that, if a given function requires computation time T for a k -tape realization, then it requires at most computation time T log T for a two-tape realization. The proof of this fact is constructive; given any k -tape machine, it is shown how to design an equivalent two-tape machine that operates within the stated time bounds. In addition to being interesting in its own right, the trade-off relation between number of tapes and speed of computation can be used in a diagonalization argument to show that if T ( n ) and U ( n ) are two time functions such that inf T ( n ) log T ( n ) ÷ U ( n ) = 0 then there exists a function that can be computed within the time bound U ( n ) but not within the time bound T ( n ).

This paper investigates 1) the problem of finding lower bounds on the computation times of on-line Turing machines, and 2) the trade-off relationship between computation time and tape dimensionality. It considers problems in which a Turing machine is supplied with a sequence of inputs representing data to be stored on the machine's tape(s), followed by a sequence of inputs requesting the machine to find and examine various portions of the stored data. The approach taken is to assume that the machine has been designed to read in and store data in such a way as to minimize the time required to subsequently locate arbitrary portions of that data. This approach sometimes makes it possible to find good lower bouds on the computation time (number of machine steps) needed to process the portion of the input sequence that calls for the retrieval of data. It is shown that there are some problems in which an increase in tape dimensionality appreciably reduces the computation time needed. But it is already known that increasing the number of a machine's tapes (beyond two) does not appreciably decrease the computation time needed. Thus, tape dimensionality and tape multiplicity are parameters that affect computation time in basically different ways.