Question

Which among the following is not true for 2-way infinte TM?

(a) tape in both directions

(b) Leftmost square not distinguished

(c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.

(d) None of the mentioned

I got this question in an internship interview.

Origin of the question is Non Deterministic Turing Machines topic in division Introduction to Turing Machines of Automata Theory

Answer 1

Right answer is (d) None of the mentioned

To elaborate: All of the mentioned are correct statements for a two way infinite tape turing machine. Theorems say the power of such a machine is in no way superior than a standard turing machine.