It is known that the languages decided by logarithmic-space Turing machines are exactly those decided by finite automata with multiple, bidirectional (2-way) scanning heads. Where could I find a proof?
$\begingroup$
$\endgroup$
3
-
5$\begingroup$ Maybe cstheory.stackexchange.com would be a more logical place to ask this. (Note: if you do cross-post, remember to add a link to each version from the other.) $\endgroup$– Gro-TsenCommented Jun 1, 2022 at 20:57
-
1$\begingroup$ @VilleSalo Are you suggesting the result is not actually true? It is, and it's not difficult to prove. Using the same idea as for simulation of Turing machines by counter machines, you can replace each work-tape by a pair of counters encoding the content of the tape. Since the tapes were $O(\log n)$ space, each counter goes up to $n^c$ for some constant $c$. Thus, you can simulate it by positions of a $c$-tuple of heads on the input tape, representing the counter in base $n$. Note that your $k$ depends on the machine, it's not bounded by a universal constant. $\endgroup$– Emil JeřábekCommented Jun 2, 2022 at 10:58
-
$\begingroup$ You are right. Not my week. $\endgroup$– Ville SaloCommented Jun 2, 2022 at 14:08
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
The following paper contains a proof (p. 191-192):
Sudborough, I. H. Some remarks on multihead automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 11.3 (1977): 181-195.
In the introduction, it mentions that the result is originally proved in
J. Hartmanis. On Nondeterminancy in Simple Computing Devices. Acta Informatica, 1, 1972, 336-344.
(The second paper does not seem to be available online though).
answered Jun 3, 2022 at 9:23