Proof of Turing Completeness for a stack-based language

Question

I'm writing a joke language that is based on stack operations. I've tried to find the minimum amount of instructions necessary to make it Turing complete, but have no idea if a language based on one stack can even be Turing complete. Will these instructions be enough?

IF (top of stack is non-zero)
WHILE (top of stack is non-zero)
PUSH [n-bit integer (where n is a natural number)]
POP
SWAP (top two values)
DUPLICATE (top value)
PLUS (adds top two values, pops them, and pushes result)

I've looked at several questions and answers (like this one and this one) and believe that the above instructions are sufficient. Am I correct? Or do I need something else like function calls, or variables, or another stack?

If those instructions are sufficient, are any of them superfluous?

---

EDIT: By adding the ROTATE command (changes the top three values of the stack from A B C to B C A) and eliminating the DUPLICATE, PLUS, and SWAP commands it is possible to implement a 3 character version of the Rule 110 cellular automaton. Is this sufficient to prove Turing completeness?

If there is an example of a Turing complete one-stack language without variables or functions that would be great.

Answer 1

If you want to prove that your language is Turing complete, then you should look at this Q&A on the Math StackExchange site.

• How to Prove a Programming Language is Turing Complete?

One approach is to see if you can write a program using your language that can simulate an arbitrary Turing Machine. If you can, that is a proof of Turing completeness.

---

If you want to know if any of those instructions are superfluous, see if you can simplify your TM emulator to not use one of the instructions.

But if you want to know if a smaller Turing complete language is possible, look at SKI Combinator Calculus. Arguably, there are three instructions: the S, K and I combinators. And I is apparently redundant.