5. (a) Draw a diagram for a register machine that tests whether a given number n is divisible by 3. Your machine should

[answerhappygod]

5 A Draw A Diagram For A Register Machine That Tests Whether A Given Number N Is Divisible By 3 Your Machine Should 1 (43.36 KiB) Viewed 64 times

5. (a) Draw a diagram for a register machine that tests whether a given number n is divisible by 3. Your machine should have two registers A and B, with the input n supplied in A, and B initialized to 0. Your machine should have just a single exit point, and the value of B on exit should be 1 if n is divisible by 3, 0 otherwise. Each junction between basic components should be marked with an arrowhead, as in the examples in lectures. It does not matter if the value of n is lost in the course of the computation. (b) Would you expect it to be possible to build a register machine that tests whether a given number n is prime? Very briefly justify your answer, draw- ing on any relevant statements from lectures. (Do not attempt to construct such a machine explicitly.)