3 ms·

If I read the spec correctly, this is not necessarily Turing complete because there is only one stack and the number is not explicitly unbounded. (You can achie

If I read the spec correctly, this is not necessarily Turing complete because there is only one stack and the number is not explicitly unbounded. (You can achieve TC with two stacks of bounded numbers or one stack of unbounded numbers though.) In particular JavaScript implementation uses an ordinary JS number, which is essentially bounded. The original TC claim [1] seems dependent to another language (Volatile) which uses explicitly unbounded numbers. [1] https://esolangs.org/w/index.php?title=StupidStackLanguage&diff=68661&oldid=68659 https://esolangs.org/w/index.php?title=StupidStackLanguage&d...

CJefferson 6y ago
I assume the other way, if integers aren't limited, assume they are unbounded. They are in the Python implementation. If you start worrying about implementation bounds, C gets iffy -- pointers have to have a known size, and be convertable to and from integers, so you cant have unbounded memory in any given implementation (you can get closer with files, but files still have offsets which imply limited maximum size, and there is a limited space of possible strings to name files).
- giomasce 6y ago
  That's true for any language. Computers are finite state machines, though with a lot of states, therefore no actual computer can really run a Turing complete language. As many mathematical things, Turing completeness is an abstraction that doesn't really map on reality without caveats.
- lifthrasiir 6y ago
  You are correct. For this reason esolang community actually has defined a related concept called bounded-storage machine (BSM) [1]. C has a bounded memory but it can simulate an arbitrary large BSM by increasing memory and thus pointer size, so it is very close to (but not exactly) TC. By comparison SSL has two axes of bounds (stack length bounds and number bounds), only one of which is useful for simulating an arbitrary large BSM. I would say it is also close to TC but less so than C, because you need number bounds proportional to the max memory of simulated BSM and it is much easier to hit number bounds than stack length bounds. [1] https://esolangs.org/wiki/Bounded-storage_machine https://esolangs.org/wiki/Bounded-storage_machine
asplake 6y ago
Make it case-sensitive, case denoting which one of two stacks to use? Curious: Does that make the language easier to use in any way? (“Easier” here being very relative of course)
- alpaca128 6y ago
  But wouldn't that require additional instructions to exchange values between the two stacks? Otherwise you'd basically just run two independent programs at the same time. In theory you could just replace a single letter's functionality with "push first element to other stack". v and w are redundant, for example.
  - lifthrasiir 6y ago
    You can put only ones and zeros to two stacks and branch against one stack to manipulate another stack. This is enough for simulating a two-symbol tape and thus any TM operating on that tape.

CJefferson 6y ago

I assume the other way, if integers aren't limited, assume they are unbounded. They are in the Python implementation. If you start worrying about implementation bounds, C gets iffy -- pointers have to have a known size, and be convertable to and from integers, so you cant have unbounded memory in any given implementation (you can get closer with files, but files still have offsets which imply limited maximum size, and there is a limited space of possible strings to name files).

giomasce 6y ago
That's true for any language. Computers are finite state machines, though with a lot of states, therefore no actual computer can really run a Turing complete language. As many mathematical things, Turing completeness is an abstraction that doesn't really map on reality without caveats.
lifthrasiir 6y ago
You are correct. For this reason esolang community actually has defined a related concept called bounded-storage machine (BSM) [1]. C has a bounded memory but it can simulate an arbitrary large BSM by increasing memory and thus pointer size, so it is very close to (but not exactly) TC. By comparison SSL has two axes of bounds (stack length bounds and number bounds), only one of which is useful for simulating an arbitrary large BSM. I would say it is also close to TC but less so than C, because you need number bounds proportional to the max memory of simulated BSM and it is much easier to hit number bounds than stack length bounds. [1] https://esolangs.org/wiki/Bounded-storage_machine https://esolangs.org/wiki/Bounded-storage_machine

asplake 6y ago

Make it case-sensitive, case denoting which one of two stacks to use? Curious: Does that make the language easier to use in any way? (“Easier” here being very relative of course)

alpaca128 6y ago
But wouldn't that require additional instructions to exchange values between the two stacks? Otherwise you'd basically just run two independent programs at the same time. In theory you could just replace a single letter's functionality with "push first element to other stack". v and w are redundant, for example.
- lifthrasiir 6y ago
  You can put only ones and zeros to two stacks and branch against one stack to manipulate another stack. This is enough for simulating a two-symbol tape and thus any TM operating on that tape.