On-Line Turing Machine Computations

Abstract

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.