Is it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers.
I failed to find any examples or explanations. If it is possible, how?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this communityIs it possible to simulate a stack-based machine using a 1-tape turing machine? I cannot wrap my head around it as turing machines do not provide mechanisms such as pointers.
I failed to find any examples or explanations. If it is possible, how?
Machines that have only a stack are called pushdown automata. They are less powerful than Turing machine, so yes: TMs can simulate stacks.
Turing machines are a fairly simplistic model of computation, which can make programming in them hard. Try to start with simple things; for instance, implement a counter. If you feel ambitious, try implementing the basic building blocks of (Turing-complete) imperative programming as Turing machines. This should convince you, then, that TMs are as powerful as any other¹ model.
As for your question, you don't need pointers for a stack. TM tapes have a direction, and you can easily label cells by introducing special alphabet symbols; the TM can then move over the tape and look for these labels. It's all a matter of encoding.
In addition to what @Raphael said, it's very easy to actually do it. Just make a rule for your Turing Machine that every time it moves left, it will also write null. Voilà! You have made a Pushdown Automata.