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?
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.
A language based only on a single stack can't be Turing complete (unless you "cheat" by allowing stuff like temporary variables or access to values "deeper" in the stack than the top item). Such a language is, as I understand it, equivalent to a Pushdown Automata, which can implement some stuff (e.g. context-free grammars) but certainly not as much as a full Turing machine.
With that said, Turing machines are actually a much lower bar than you'd intuitively expect - as originally formulated, they were little more than a linked list, the ability to read and modify the linked list, and branching. You don't even need to add all that much to a purely stack-oriented language to make it equivalent to a Turing machine - a second stack will technically do it (although I certainly wouldn't want to program against it), as would a linked list or queue.
Correct me if I'm wrong, but I'd think that establishing that you can read from and write to memory, can do branching, and have at least one of those data structures (two stacks, one queue, one linked list, or the equivalent) would be adequate to establish Turing completeness.
Take a look, too, at nested stack automata.
You may also want to look at the Chomsky hierarchy (it seems like you may be floating somewhere in the vicinity of a Type 1 or a Type 2 language).
(The one point I'm glossing over here is the fact that the original model didn't include any constraints on memory consumption, so the linked list was allowed to be arbitrarily large. Obviously, this isn't true on a real computer, so technically Linear bounded automata is a somewhat more realistic model of a real computer).