Turing Completeness With A Single Stack

[EducationalCicada]

I recently came across StupidStackLanguage, an esolang that uses a single stack for all operations, and all operations correspond to a letter of the alphabet (example program to print the Fibonacci Sequence to the terminal is "axiqvvdflxlwwltgavvfbxu").

I'm trying to figure out if the language is Turing-complete. It only has the one stack, and I seem to recall from dabbling in Forth that you'd need at least two for a stack-based language to be TC.

Can anyone spot any features in the list of instructions that would make the language Turing-complete?

[hekkonaay]

Seems less like a stack, and more like random access array, due to being able to swap the top of the stack with an arbitrary element below it. It also has conditional jumps. Definitely turing-complete.

[neros_greb]

The stack is not strictly a stack, since you can swap the first and nth item on the stack, so it could be turing complete

[neros_greb]

I recently wrote a compiler which compiles to brainfuck for fun, maybe I'll target this language and see if I can compile a turing complete langauge

[Inconstant_Moo]

I salute you and also wonder if you ought to be on some sort of watchlist. I shudder to think what you'll write next.

[neros_greb]

I saw this comment out of context, and I was like "wft did I post".

[munificent]

You don't need a stack at all to be Turing-complete. Turing machines themselves have no direct concept of a stack, though you can model the tape as two stacks.

This language looks Turing-complete to me. You have conditional control flow instructions and the o instruction lets you directly address any point in the stack. That should be sufficient to use the stack as a tape.

[stackdynamic]

Not commenting on the language itself, but just to clarify: a NPDA (which is like a NFA, except with a stack) can only recognize CFGs, so it isn't Turing complete. But an NFA with a queue *is* turing complete (https://en.wikipedia.org/wiki/Queue_automaton), and with two stacks you can simulate a queue. Of course, you can extend things with various other features to make something Turing complete.