Answer Happy

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. [7 marks (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.) [3 marks)