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?
$\begingroup$
$\endgroup$
Add a comment
|
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
2
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.
-
$\begingroup$ Thank you for your answer. I actually need to design a simulation for a machine supporting both a stack and registers. $\endgroup$ – just.kidding Apr 25 '17 at 19:03
-
$\begingroup$ @just.kidding Building a simulator for "modern" machine architectures is definitely possible, but not very interesting (by my estimation). $\endgroup$ – Raphael♦ Apr 25 '17 at 20:28
