Timeline for Multi-head two-way finite automata versus logarithmic space
Current License: CC BY-SA 4.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 3, 2022 at 9:23 | answer | added | Damiano Mazza | timeline score: 3 | |
| Jun 2, 2022 at 14:08 | comment | added | Ville Salo | You are right. Not my week. | |
| Jun 2, 2022 at 10:58 | comment | added | Emil Jeřábek | @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. | |
| Jun 2, 2022 at 5:31 | history | edited | Emil Jeřábek |
edited tags
|
|
| Jun 1, 2022 at 20:57 | comment | added | Gro-Tsen | 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.) | |
| S Jun 1, 2022 at 20:36 | review | First questions | |||
| Jun 2, 2022 at 2:39 | |||||
| S Jun 1, 2022 at 20:36 | history | asked | Matt | CC BY-SA 4.0 |