# Simulating nondeterministic RAM with nondeterminstic turing machine

Nondeterminstic RAM is like deterministic RAM with extra instruction “JMAYBE” which nondeterministically jump or continue when executed.

According to this paper: An $$O(T \log T)$$ reduction from RAM computations to satisfiability I guess that we can simulate nondeterministic RAM on nondeterministic TM , with only logarithmic overhead. But this paper also has an important refrence which i could not find “J. Wiedermann, Deterministic and nondeterministic simmulation of RAM by the Turing machine, (IFIP 1983 Paris)”. My question is , how i can show that:

If a language $$A$$ is recognized by a nondeterministic RAM $$P$$ within time $$T(n)$$ and if $$P$$ has $$l(n)$$ logarithmic, then $$A$$ is recognized by some nondeterministic multitape Turing machine within time $$\log T(n) . T(n)$$

The function $$l(n)$$ is associated with the machine, it denotes the time required to store the number $$n$$. here we assume $$l(n) = \lceil \log |n| \rceil$$.

This is my homework and i struggle with this question about one week (at first i learned about RAM model) , but i could not figure out how this simmulation is possible, and also i did not find any thing useful. All i know is , there is a naive simmulation which its overhead is quadratic.

• I don't understand what is meant by $P$ has $l(n)$ logarithmic. Since this is homework, have you tried asking your instructor for help on how to approach this?
– D.W.
Jun 22 at 20:13
• @D.W. I clearify what i meant by that in edited question. Since i thought maybe there is an obvious point which i missed here, i did not ask him yet. I thought maybe i could get some hints from this community. Jun 22 at 22:05

Here is your hint. Imagine that we augment $$P$$ to record a log of all the random-access reads and writes $$P$$ does to memory (i.e., for each read, record the address and the value that was read; for each write, record the address and the value that was written), in the order they were done. At the end of the computation, could you efficiently verify whether that log is self-consistent and correct? What would be the running time of an algorithm designed to verify the log?
• If $P$ augmented by a log of all random-access reads and writes $P$ does to memory (in order), then i have to verify that.So i have to look for writes to an address $a_i$ which does not match to their consecutive reads from the same address: $\dots\# (write,a_i,v_i) \# \dots \# (read,a_i,v_j)$ s.t. $v_i \neq v_j$. Also i have to check that first reads from $a_i$ (No wirtes before) to be value of $0$, because at first all the values are $0$.So i have to remember the values and that takes alot of time (maybe with stack?).i thought that maybe i have to use nondeterminism to verify it efficiently? Jun 26 at 15:24
• @OmidYaghoubi, What would be the running time of an algorithm designed to verify the log? Hint: an answer should be something like $O(n)$ or $O(n^2)$ or $O(2^n)$, not "alot of time". Can you think of any way to do it efficiently? If not, I suggest you spend some more time pondering how you might approach that.