Skip to main content
3 of 5
added 838 characters in body; deleted 1 character in body

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 a 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)$

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.