7
$\begingroup$

(Cross-posted from cstheory-stackexchange)

The following fact seems to be used implicitly in cs theory, particularly algorithms. Given a RAM machine $M$ running in time $O(f(n))$, another RAM machine $M′$ can simulate $M$ in time $O(f(n))$. This differs from the case for Turing machines, where $M′$ may require $O(f(n) \log(f(n))$ time.

I say this is often used implicitly because many papers will simply say something like "run $M$, but keep track of certain auxiliary information as you do so". This is really simulating $M$, but for RAM machines the distinction is not so important because running times are not (asymptotically) affected.

Is there a reference for this theorem? I am summarizing the situation correctly?

EDIT:

Some questions were raised about what is meant by simulation. More precisely, that there exists a universal RAM $T$ such that, for any RAM machine $M(x)$ running in time $O(f(|x|))$, there is an encoding $e_M$ such that $T(e_m, x) = M(x)$ and $T(e_m, x)$ runs in time $O(f(|x|))$ as well. (The constant term may be different between $T$ and $M$).

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Next time please add a link when you cross-post! cstheory.stackexchange.com/questions/7391/… $\endgroup$
    – Tsuyoshi Ito
    Commented Jul 26, 2011 at 14:52
  • 3
    $\begingroup$ 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. $\endgroup$
    – Emil Jeřábek
    Commented Jul 26, 2011 at 15:27

1 Answer 1

Reset to default
2
$\begingroup$

I think that the blow-up in time can be much worse than you describe, depending on the specific computational models that are used. For example, consider the function that accepts an input string $w$ of arbitrary length and outputs the double duplicate string $ww$. On a Turing machine with separate input and output tapes having heads that can move independently, then this output can be formed in linear time, essentially copying $w$ to the output tape and then sending the input tape head back to the start, and then copying it again, which takes about $3|w|$ time altogether. But if one instead has the two tape machine model with a single head reading both tapes together, then the former computation can be simulated, but it takes a lot more time. A direct implementation will have the head necessarily making a lot of back-and-forth motions in order to form the second copy of $w$, ferrying small pieces of it back and forth, and the time complexity will rise to something like $O(|w|^2)$. And I expect that one can describe much worse examples.

This kind of issue is precisely what makes the class $P$ of polynomial time computability so conveneint and robust as a notion of feasibility. Because all the various standard computational models can simulate each other with only polynomial time factors, the choice of any particular model of computability does not affect membership in $P$ or its cousins, such as NP, which are closed under these polynomial factors.

But meanwhile, the point is that it doesn't really make sense to talk about, say, an $O(n^2)$ algorithm unless the particular model or class of models of computability has been understood. After all, one model's $O(n)$ can be another's $O(n^2)$ or worse.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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 $\endgroup$
    – Gerhard Paseman
    Commented Jul 26, 2011 at 15:20
  • 2
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Jul 26, 2011 at 16:23
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Commented Jul 26, 2011 at 16:29
  • 1
    $\begingroup$ 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. $\endgroup$
    – David Harris
    Commented Jul 26, 2011 at 18:11
  • $\begingroup$ 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. $\endgroup$
    – Joel David Hamkins
    Commented Jul 26, 2011 at 22:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .