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?
Can a 1-tape turing machine simulate a stack?
turing machines;computation models;stacks
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.Ignoring hyper-computation.