4
$\begingroup$

For stack-oriented programming language, how many top-most items of the stack are needed to be accessible in order to be Turing complete?

Is it enough to be able to access just the top-most item? Two items? Three? Any item?

In the case of Forth, is it necessary to have rot, pick, roll? Why does rot operates with exactly top three items?

$\endgroup$
  • $\begingroup$ What can the "items" be? ​ If they're bounded-size, then restricting to a bounded number of items just gives you DFAs, else see this article. ​ ​ ​ ​ $\endgroup$ – user12859 Feb 24 '17 at 11:38
  • $\begingroup$ @RickyDemer I would say bounded-size, otherwise couldn't I somehow encode the rest of the stack in just one item? $\endgroup$ – Ecir Hana Feb 24 '17 at 13:30
  • $\begingroup$ @D.W. Just a guess: isn't it possible to simulate two-counter machines if I have rot, i.e. access to at least three top-most items? $\endgroup$ – Ecir Hana Feb 24 '17 at 13:32
  • $\begingroup$ @D.W. obviously, Forth has some constructs which allow it to be more powerful than a stack machine, including a second stack (the "return" stack) and random access memory. But I think your answer for a hypothetical Forth with a single stack is correct, and should be turned into an answer. $\endgroup$ – cody Feb 25 '17 at 19:25
  • $\begingroup$ @EcirHana, how would you simulate a two-counter machine using rot, if the items on the stack are of fixed size? (the counter in a two-counter machine can have arbitrarily large values) $\endgroup$ – D.W. Feb 26 '17 at 6:13
2
$\begingroup$

It depends on what kinds of things you can store on the stack.

If each item on the stack is of unbounded size, you can simulate a two-counter machine, which is Turing-complete. Therefore, in this case, you can achieve Turing-completeness with just the ability to access the top two items on the stack.

If items are bounded-size, restricting to access a bounded number of top-most items of the stack gives something equivalent in power to a PDA. (For instance, suppose all you can do is access the top 5 items of the stack, and use that together with a finite control to transition to a new state of the finite control and either push/pop. Then grouping the items into 5-tuples, we can build an equivalent machine where you only need to access the topmost item. That machine is a PDA.) Therefore, in this case, it's not Turing complete with access to any finite number of items at the top of the stack.

$\endgroup$

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.