Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
How can we convert a given Turing Machine into a Random Access Machine? I understand that we can use the transition function to come up with a sort of algorithm but how can we translate all of it into a set of instructions (load/add etc).
For example, here's a TM:
M = ({q 0 , q 1 , q accept , q reject }, {0, 1}, {0, 1, t}, δ, q 0 , q accept , q reject )
having a transition function as follows:
Now, how can I formulate a set of RAM instructions from this?
Sample Solution:
You can implement, on a RAM machine, an interpreter that simulates the behavior of an arbitrary Turing machine (that's just a matter of programming, and there's nothing conceptually interesting or difficult about it); then use it on this particular Turing machine. That's much easier to do, but might not lead to nice code for the RAM machine.
Or, you can understand/reverse-engineer the algorithm the Turing machine is using (this could be difficult), and then figure out how to implement that algorithm on a RAM machine (which is just a matter of programming once you understand the algorithm).
Asking "how do I write code on a RAM machine?" is not very different from "how do I write code in assembly language?"; you just do it, and there's not a lot of deep scientific or conceptual ideas needed, once you know what algorithms you are using.
