title: Proof of Turing Completeness for a stack-based language
body: <p>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?</p>
  
  <pre><code>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)
  </code></pre>
  
  <p>I've looked at several questions and answers (like <a href="https://stackoverflow.com/a/41205535/4810639">this one</a> and <a href="https://stackoverflow.com/questions/449014/what-are-practical-guidelines-for-evaluating-a-languages-turing-completeness#comment-4050953">this one</a>) 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?</p>
  
  <p>If those instructions are sufficient, are any of them superfluous?
  <hr>
  <strong>EDIT:</strong> By adding the <code>ROTATE</code> command (changes the top three values of the stack from <code>A B C</code> to <code>B C A</code>) and eliminating the <code>DUPLICATE</code>, <code>PLUS</code>, and <code>SWAP</code> commands it is possible to implement a 3 character version of the <a href="https://en.wikipedia.org/wiki/Rule_110" rel="nofollow noreferrer">Rule 110 cellular automaton</a>. Is this sufficient to prove Turing completeness?</p>
  
  <p>If there is an example of a Turing complete one-stack language without variables or functions that would be great.</p>