Timeline for Why do we use single tape Turing machines for time complexity?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 22, 2017 at 20:59 | comment | added | Dan Brumleve | Keeping the tape heads in place it seems like we can make total energy loglinear or hopefully no worse than quasilinear in time by engineering a form of the Hennie-Stearns construction. I'm imagining the tapes rolled into increasingly larger loops as they extend in either direction... Or more imaginatively, on spools of tapes, 100 tapes to a spool, 100 spools to a rack, 100 racks to a warehouse, and on and on. Of course for bounded energy per iteration we'd need total energy linear in time. But quasilinear is better than the naive quadratic so I thought I would mention it. | |
| Apr 10, 2012 at 21:20 | comment | added | Kaveh | I was expecting theoretical reasons (not realizibility of the models) but I find this answer very interesting, so I am accepting it. Thanks again. | |
| Apr 10, 2012 at 21:18 | vote | accept | Kaveh | ||
| Apr 8, 2012 at 1:29 | comment | added | Sasho Nikolov | i thought that Turing was trying to abstract the concept of "computing" and not abstracting a model for a physical device. in that case, a single-tape Turing machine captures cleanly the philosophical intuition that computation involves local access to large (infinite) memory | |
| Apr 7, 2012 at 22:49 | history | answered | matus | CC BY-SA 3.0 |