Question

A Turing machine with doubly infinite tape is similar to an ordinary Turing machine, but its tape is infinite to the left as wellas to the right The tape is initially filled with blanks except for the portion that contains the input. Computation is definedas usual except that the head never encounters an end to the tape as it moves leftward. Show that this type of Turingmachine recognizes the class of Turing- recognizable languages.

Answer 1

Use multitape Turing machine to simulate doubly infinite one

Step-by-step explanation:

It is obvious that Turing machine with doubly infinite tape can simulate ordinary TM. For the other direction, note that 2-tape Turing machine is essentially itself a Turing machine with doubly (double) infinite tape. When it reaches the left-hand side end of first tape, it switches to the second one, and vice versa.