202211171811
Type :Note Tags : Theory of Computation
Two-Way Infinite Tape Turing Machine
Two-way Infinte tape does not add any power. we can just break it and put it back together such that the two halfs are now two tracks of a semi-infinte tape
The bottom track will be used to simulate the machine when the head is on the left of the fold, and the top track will be used when the head is on the right.
Related Problems
Turing Machines with multiple tapes