Logic : Turing Machines

Please see the attached file for the fully formatted problems.

(a) We wish to design a Turing machine which, using monadic notation, inputs a
pair (in, n) of positive integers in standard starting position (on an otherwise blank tape), and which halts scanning the rightmost of a string of in is on an otherwise blank tape.
Write down which of the following Turing nuchines is suitable for this task. For each machine which is unsuitable, explain why it is unsuitable this explanation can take the form of a sequence of configurations for appropriate test data.
.….
(b) Devise and give the flow graph of a Turing machine which, if started scanning the rightmost of a string of n is (on an otherwise blank tape). would halt scanning a single 1 on an otherwise blank tape.
.….
In this question, we consider the Turing machine 31 with the flow graph below.
...
(a) Write down the machine table for 31. [2]
(b) For each of the following starting configurations of the machine 31. write down the sequence of configurations for the subsequent computation.
(i)0110 (ii) 01110 (iii)0111110
...
(c) The machine 31 has been designed to take as input a positive integer in monadic notation and to output an integer also in monadic notation. Thu.s the machine computes the values of a function!': P -> N.
(i) Wnte down the values of f(l),f(2),f(3),f(4),f(5). [2.5]
(ii) What, in general. is the value off(n) for vs Є p Describe briefly how the machine computesJ(n), including an indication of each possible halting state and the circumstances under which it halts there.
.….

Attached file(s):

brainmass logic.doc  View File