Timeline for RAM simulating another RAM
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 26, 2011 at 18:15 | history | edited | David Harris | CC BY-SA 3.0 |
added 359 characters in body
|
| Jul 26, 2011 at 15:27 | comment | added | Emil Jeřábek | I found the question too vague to admit a sensible answer. You can simulate any machine in time $O(f(n))$ by just running it as is (this is true even for Turing machines, as long as you have enough tapes). Thus, the answer to the question depends completely on the nature of the unspecified "auxiliary information" you need to track. You'll fit within $O(f(n))$ as long as the simulation of each step takes $O(1)$ steps of the simulating machine (at least amortized), but this is not a necessary condition. | |
| Jul 26, 2011 at 15:13 | answer | added | Joel David Hamkins | timeline score: 2 | |
| Jul 26, 2011 at 14:52 | comment | added | Tsuyoshi Ito | Next time please add a link when you cross-post! cstheory.stackexchange.com/questions/7391/… | |
| Jul 26, 2011 at 14:32 | history | asked | David Harris | CC BY-SA 3.0 |