A Turing machine with doubly infinite tape is similar to an

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 tape as it moves leftward. Show that this type of Turing machine recognizes the class of Truing-recognizable languages.

For questions 3 to 5, remember that a Turingmachine starts in state 1, reading the leftmost nonblank cell.
1. Given the Turingmachine 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

Please see the attached file for the fully formatted problems.
(a) We wish to design a Turingmachine 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.
W

Construct a turingmachine 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.

Consider the problem of testing whether a Turingmachine 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.

Write a Turingmachine 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 Turingmachine algorithm, include comments for each instruction or related group of instructions.

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)

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 Turingmachine is equipped with the following:
(i) a tape that is infinitely lon

Devise a Turingmachinewith input given in unary notation (i.e., a string of n 1's denotes the integer n, and numbers are delimited by 0's) such that the machine produces the following output:
0 if x is divisible by 4
1 if x is congruent to 1 modulo 4
2 if x is congruent to 2 modulo 4
3 if x is congruent to 3 modulo

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