On heads versus tapes
type: Item
instance of: scholarly article
title: On heads versus tapes
zbMATH Open document ID: 0536.68050
DOI: 10.1016/0304-3975(83)90063-4
published in: Theoretical Computer Science
publication date: 1984-01-01T00:00:00Z
review text: 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)].
Mathematics Subject Classification ID: 68Q05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3852436
zbMATH Keywords: real-time computation
zbMATH Keywords: real-time simulation
zbMATH Keywords: d-dimensional Turing machine
zbMATH Keywords: descriptional complexity of rectangular figures
author: Wolfgang J. Paul
reviewed by: Daniele Mundici
MaRDI profile type: Publication
full work available at URL: 0304-3975(83)90063-4
OpenAlex ID: W2029121016
cites work: Q4077448
cites work: Real-Time Simulation of Multihead Tape Units
cites work: New Real-Time Simulations of Multihead Tape Units
cites work: k-Band-Simulation von k-Kopf-Turing-Maschinen. (k-tape simulation of k- head Turing machines)
Recommended article: Two heads are better than two tapes
Recommended article: On long runs of heads and tails
Recommended article: On long runs of heads and tails. II
Recommended article: Head-Media Interaction in Magnetic Recording
Recommended article: Head-media interaction in magnetic recording
description: scientific article; zbMATH DE number 3852436