Question

Can a single tape turing machine be simulated using deterministic 2-stack turing machine?

(a) Yes

(b) No

(c) Cannot be said

(d) none of the mentioned

This question was posed to me by my school principal while I was bunking the class.

This interesting question is from Multistack Machines, Counter Machines in portion Introduction to Turing Machines of Automata Theory

Answer 1

Correct choice is (a) Yes

Explanation: The symbols to left of the head of turing macine being simulated can be stored on the stack while the symbols on the right of the head can be placed on another stack. On each stack, symbols closer to the TM’s head are placed closer to the top of the stack than symbols farther from the TM’s head.