Timeline for What Turing-Complete models of computation carry a notion of time complexity that "agrees" with that of Turing Machines?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:48 | history | edited | CommunityBot |
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
|
|
| Feb 13, 2014 at 8:10 | history | edited | Thomas Klimpel | CC BY-SA 3.0 |
Added a reference to recent results regarding the solution of the question with respect to write only devices.
|
| Feb 12, 2014 at 23:25 | history | made wiki | Post Made Community Wiki by Thomas Klimpel | ||
| Feb 12, 2014 at 22:05 | comment | added | Todd Trimble | It's not at all clear how this answers the question. It might make sense to make this response CW. | |
| Feb 12, 2014 at 15:00 | comment | added | Joel David Hamkins | Punchtape Turing machines, for which the machine can mark each cell at most once, punching a hole in the paper tape or not, are like your write-once-read-many machines, and have been investigated. Punchtape machines are Turing complete, and have been investigated, but I find it likely that there is a substantial time cost. | |
| Dec 14, 2013 at 13:21 | history | answered | Thomas Klimpel | CC BY-SA 3.0 |