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.
.....

For questions 3 to 5, remember that a Turing machine starts in state 1, reading the leftmost nonblank cell.
1. Given the Turing machine instruction
(1,1,0,2,L)
and the configuration
... b 1 0 b ... (Tape read head is in state 1, and is over symbol 1 on the left)
Draw the next configuration.
2. A Tur

A Turing machine with doubly infinite tape is similar to an ordinary Turing machine except that its tape is infinite to the left as well as to the right. The tape is initially filled with blanks except for the portion that contains the input. Computation is defined as usual except that the head never encounters an end to the t

Construct a turing machine to compute the product x*y of any two positive integers x and y. Assume that the inputs x and y are represented in unary and are separated by a single 0.

Write a Turing machine algorithm to perform a unary decrement. Assume that the input number may be 0, in which case a single 0 should be output on the tape to signify that the operation results in a negative number.
When writing Turing machine algorithm, include comments for each instruction or related group of instructions.

Think of five questions that you would use if you were acting as the interrogator of a Turing test. Why would a computer have difficulty answering them well? How would answering, or not answering, these questions help you determine if your subject was a computer or a human being?

Give the transitions for a turing machine that accepts the language given below.
L = {AnBnCn : n>=1}
Where,
An denotes a raised to the power n (a^n)
Bn denotes b raised to the power n (b^n)
Cn denotes c raised to the power n (c^n)

Psychologist Stevan Harnad has proposed the Total Turing Test for artificial intelligence. To pass this test, the computer being tested would have to be able to do everything that a normal human being does, including walking, riding a bicycle, swimming, dancing, playing a musical instrument, and so on. Only a computer with a rob

Consider the problem of testing whether a Turing machine M on an input w ever attempts to move its head left when its head is on the left-most tape cell. Formulate this problem as a language and show that it is undecidable.

Consider the following Turing-machine model (which is used in one of the standard textbooks in recursion theory, a branch of mathematical logic: Recursively Enumerable Sets and Degrees, by Robert I. Soare, Springer-Verlag, New York, 1987):
The Turing machine is equipped with the following:
(i) a tape that is infinitely lon