Size Arguments in the Study of Computation Speeds

In this paper we use arguments about the size of the computed functions to investigate the computation speed of Turing machines. It turns out that the size arguments yield several new results which we have not been able to obtain previously by diagonalization. For example, we show that for arbitrarily complex running times $T(n)$ there exist functions which can be computed on a one-tape Turing machine in time $T(n)$ but not in time $t(n)$ provided $\stackrel{\lim}{n \rightarrow \infty} \frac{t(n)}{T(n)}=0$. The same result is also shown to hold for many-tape machines. We show furthermore, that there exist arbitrarily complex computations for which one-tape machines are slower than two-tape machines by a factor equal to the logarithm of the computation time of the two-tape machine. We conclude by discussing several other computational complexity measures and compare results obtained by diagonalization and size arguments