On heads versus tapes (Q792093): Difference between revisions

The author proves the following theorem: For all k and \(d\geq 2\), d- dimensional k-tape Turing machines (with any number of additional linear tapes) cannot simulate in real time Turing machines with k heads on one d-dimensional tape. For \(k=2\) the theorem cannot be improved. For the proof the author develops a theory of descriptional complexity of rectangular figures, using such tools as Kolmogorov complexity, and Chaitin randomness. Part of the theory is implicit in the article by \textit{W. J. Paul, J. I. Seiferas} and \textit{J. Simon} [Proc. 12th ACM Symp. Theory of Computing, 357-367 (1980)]. The author also compares his theorem with known simulation results due to \textit{P. C. Fischer, A. R. Meyer} and \textit{A. L. Rosenberg} [J. Assoc. Comput. Mach. 19, 590-607 (1972; Zbl 0261.68027)], \textit{B. L. Leong} and \textit{J. I. Seiferas} [ibid. 28, 166-180 (1981; Zbl 0454.68033)], \textit{W. Schnitzlein} [Abt. Naturw. Univ. Konstanz (1981; Zbl 0507.68025)] and \textit{H.-J. Stoß} [Computing 6, 309-317 (1970; Zbl 0222.02036)].