Crossing sequences and off-line turing machine computations

This paper is concerned with the computations performed by one-tape, off-line Turing machines. It introduces the idea of a "crossing sequence", and shows how such sequences can be used to analyze the behavior of off-line machines. It describes a class of recognition problems for which good estimates of computation time can be obtained by arguments based on the properties of crossing sequences. It shows that the square-law bounding relationship between the computation times of one- and two-tape machines can actually be met. Finally, it considers the amount by which the computation time of a one-tape, off-line machine must be increased in order to increase the computing abilities of such a machine.