Timeline for RAM simulating another RAM
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 26, 2011 at 22:48 | comment | added | Joel David Hamkins | I guess the same phenomenon arises with multiple tapes, if $M$ has the same number of tapes as $M′$ and the same alphabet, since in order to undertake the simulation and do its own side calculations about it (looking for a feature in it, say), the machine would seem to have to go to a separate part of the tape and back while performing the simulation, which would seem to add a linear factor to the time. | |
| Jul 26, 2011 at 22:13 | comment | added | Joel David Hamkins | David, I agree that it is extremely common (and extremely important) to analyze the precise running time of algorithms, and indeed this is often done. My point was only that your claim that a Turing machine $M'$ can simulate another $M$ (while also doing something else) in time $O(f(n)\log(f(n)))$ is not correct for all Turing machines. For single-tape Turing machines with a single head, in order for $M'$ to simultate $M$ and also do side computation, it will have to do a lot of back and forth, which will push the time up at least to quadratic, exceeding your bound when $f$ is subquadratic. | |
| Jul 26, 2011 at 18:11 | comment | added | David Harris | In computer science, it is extremely common to analyze running times of algorithms more precisely than up to polynomial factors. For example, there is a celebrated paper by Tarjan which shows that the disjoint-set structure has a running time which is not quite linear, but differs by the inverse of the Ackerman function. Usually, these algorithms are described in terms of "naive operations," but technically these results are for RAMs. I would say that the RAM model is the "default" computational model for algorithms papers. | |
| Jul 26, 2011 at 16:29 | comment | added | Kaveh | e.g. we have quadratic lowerbounds for palindromes and many other problems (using communication complexity arguments) on single tape TMs but these work only up to quadratic time and only on single tape machines. I think it is still open that even SAT is not solvable in deterministic linear time. | |
| Jul 26, 2011 at 16:23 | comment | added | Kaveh | The sub-quadratic-time single tape TM is a very special case, see for example this: cstheory.stackexchange.com/questions/4928/…, but for multiple tape or super quadratic time the notions are more robust, see Peter van Emde Boas's article "Machine Models and Simulation" in TCS handbook. | |
| Jul 26, 2011 at 15:20 | comment | added | Gerhard Paseman | Indeed what you say is true for TM's. Is it true for RAM's? I suspect not because the access times are different, but I don't know. Gerhard "Ask Me About System Design" Paseman, 2011.07.26 | |
| Jul 26, 2011 at 15:13 | history | answered | Joel David Hamkins | CC BY-SA 3.0 |