I understand how RAM commands work but I am unable to understand how we use a given input string and find the output. For instance,

there's a Random Access Machine which has an input {0,1}*. The program logic is as follows:

1: read

2: store 1

3: read

4: add 1

5: read

6: add 1

7: load 1

8: if a=2 go to 11

9: print 0

10: goto 12

11: print 1

12: end

Now, on the input tape we have i=11101011. How can I find the content of the output tape? What's the approach?

When we see read, do we only read the first character? If yes, then what exactly do we add 1 to? Is the output also supposed to be in binary?


Check your definitions. Often the convention is "input is the contents of memory positions 0 to $n$", result might be e.g. accept if register 0 is non-zero when the RAM halts.

  • $\begingroup$ @x89, in language/automata theory, the output is usually taken as (some indication of) "yes" (acceptance) or "no" (reject). You are of course free to e.g. stipulate that the output is the contents of the first memory positions (interpreted e.g. as an UTF string ended by a 0). $\endgroup$ – vonbrand Aug 18 '20 at 13:18

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.