A Turing machine with doubly inﬁnite tape is similar to an ordinary Turing machine, but its tape is inﬁnite to the left as wella

Question

4 years ago

11

A Turing machine with doubly inﬁnite tape is similar to an ordinary Turing machine, but its tape is inﬁnite to the left as wella

s to the right The tape is initially filled with blanks except for the portion that contains the input. Computation is deﬁnedas 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.

Mathematics

1 answer:

atroni [7] · Answer 1 · 2021-11-07T12:37:41+03:00

Answer:

Use multitape Turing machine to simulate doubly infinite one

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.