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

Let A be a turing-recognizable language consisting of descriptions of Turingmachines, {M1, M2,...}, where every Mi is a decider. Prove that some decidable language D is not decided by any decider Mi whose description appears in A. (Hint: You may find it helpful to consider an enumerator for A.)

Give the transition list for a turing machine that will determine whether for an input sequence w over symbol set {0,1}, n0(w) = n1(w).
n0(w) and n1(w) respectively indicate the count of 0s and 1s in the word 'w'.

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

Cognitive scientists believe there is an infinite potential variety of human behavior. However, they also believe that this infinite behavior is produced by a finite devise, such as the Turing machine. How can these two views be reconciled?

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)