For off-line one-tape Turing machines the number of tape reversals required for various computations may be uniformly reduced by an arbitrary constant factor.
Introduction
In the studies of specific measures of computational complexity it has always been of interest to determine the "speed-up" characteristics of such measures with respect to a class dr' of abstract computing devices [4], [6], [8]- [10]. More precisely, a speed up by a recursive function g(x) is possible if given any abstract computing device M c.//, there exists another device M'~ ~r such that M and M' have equivalent input-output behavior and for any w, g(C'w) ~ C~ for all but a finite number of w. Cw and C;~ denote the complexity measures for the computations of M and M', respectively, with w as input in each case.
M. Blum has shown that, for any measure of complexity satisfying very general conditions and for any recursive g(x), there exist computations which may be sped up by g(x) [1]. Other computations, however, may not necessarily be sped up at all with respect to the same measure. For the specific measures of computational time and storage space on multitape Turing machines, it has been shown that all computations may be sped up by a constant factor [8], [10]. x For the measure of space on multiple counter machines a speed up by any polynomial p(x) is possible [5].