[Math] two way infinite turing machine

computabilitycomputer scienceturing-machines

A Single tape turing machine is generally unbounded to right and starts from left. Read/write head moves to right from left after consuming a symbol. But what if we make left side unbounded too and make read/write head movable in both the directions? Will it increase it's power?

edit : Actually it's been answered at cs.stackexchange.com
Answer is Yes they are Equal in Power, can be simluated by one another.
Link is https://cs.stackexchange.com/questions/22863/turing-machine-infinite-tape-in-one-or-two-directions

Best Answer

To answer your question:

This has already been answered

"In spite of the appearance of being more powerful computational tool, multi-tape TM are computationally equivalent to standard TM’s with one tape."

Link to Source if you want to check authenticity

Related Question