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. Decidable languages are closed under complementation. To design a machine for the complement of a language, and simulate the machine for language on an input.
If it accepts then accept and vice versa.Decidable languages are closed under inverse homeomorphisms.
Computation is defined as usual except that the head never encounters an end to the tape as it moves leftward. There is a decidable language C consisting of Turing machine descriptions such that every machine described in has an equivalent machine in C and vice versa.
If any problem is said to be decidable if and only if when its solution is present or it can be solved by Turing machine concept, wherein out of the two Turing machines, one is A’s decider. This is because in the Turing machine has turnaround capability; it means the Turing machine can move right and left side directions and in Turing machine also has the capability of read and write in the infinite length of tape.
And this type of Turing machine recognizes the class of Turing-recognizable languages. The doubly-infinite tape can simulate an ordinary TM by just not using the portion of its tape to the left of the input.
The other direction follows from the proof that a multi-tape TM is no more powerful than a single-tape machine. A two-tape Turing machine can simulate a doubly-infinite one by using its second tape as if it were the “negative’ half of the doubly-infinite tape.
