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:

enter image description here

Now, how can I formulate a set of RAM instructions from this?

Sample Solution: enter image description here


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.

  • $\begingroup$ I added a snippet from the sample solution for this problem. I don't quite understand what we're loading and in what order. What exactly is 2 in c(o)=2. A brief explanation of the functionality would be nice. $\endgroup$
    – x89
    Aug 10 '20 at 18:22
  • $\begingroup$ @x89, That sounds tedious. I suggest you work through those details yourself. Perhaps run it by hand on some small examples. $\endgroup$
    – D.W.
    Aug 10 '20 at 18:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.