0
$\begingroup$

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?

|cite|improve this question
$\endgroup$
2
$\begingroup$

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.

  1. Ignoring hyper-computation.
|cite|improve this answer
$\endgroup$
2
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.