Question

A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but 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 Turing-recognizable languages.

Answer 1

A Turing machine with doubly infinite tape can stimulate an ordinary Turing machine. it simply marks the left hand end of the input to detect and prevent the head from moving off of that end. in order to stimulate the doubly infinite tape, Turing machine which was already shown to be equivalent in power to an ordinary 2 Turing machine. The first tape of the 2 tape Turing machine is written with the input string, and the second tape is blank. we cut the tape of the doubly infinite tape Turing machine into two parts, at the starting cell of the input string. The portion with the input string and all the blank spaces to its right appears on the first tape of the 2-tape Turing machine. The portion to the left of the input string appear son the second tape, in reverse order respectively.

Step-by-step explanation: