Talk:Stackowey
Jump to navigation
Jump to search
If anyone wonders why I undid https://esolangs.org/w/index.php?title=Stackowey&oldid=155573: I thought wrong when adding it (because I had just read the remark about C not being Turing-complete because an implementation detail slipped into the language definition. The exact same thing happened here too). The 64-bit stack element size is not even needed for most programs to still behave the same, as whatever you set the stack element size to be will still overflow if you for example do 5_+. --Lampe2020 (talk) 04:27, 11 April 2025 (UTC)
- There are still issues with the current definition and its class. There's no way to use the stack like a queue or tape and elements are implicitly bounded. At least unbounded queue behavior or unbounded elements are needed for Turing completeness. For the former, grille could be changed to index relative to the bottom of the stack, allowing for queue behavior. For the latter, technically the specification does support unbounded elements, but I believe it can lead to uncomputable behavior. The reason is the stumble command, which inverts all bits. If values are unbounded then stumble maps positive integers to their 2-adic inverse - 1. 2-adic numbers are uncomputable in general so one might assume that elements should be finite. Although, thinking about it, p-adic digit inversion and addition is probably not uncomputable when starting from naturals. stkptr (talk) 16:21, 11 April 2025 (UTC)
- Queueing is probably still possible with the from-the-top indexing that grille does, just a lot harder. Although indexing from the bottom could (if my tired brain isn't totally miscomputing right now) be made a lot easier without changing the behaviour of existing Stackowey programs by adding a command to push the stack size to the stack, so the programmer can subtract from that to go from the bottom of the stack upwards. But if you know and keep track of how many stack elements you add or remove after putting stuff in the queue you should already be able to (although quite inconveniently) handle a queue. And I added the prick command after-the-fact when I realized there is basically no good way to discard a stack element, so adding another command for pushing the stack size to the stack (also a way to reliably get random numbers by copying a number from the (stacksize+1):th place in the stack) wouldn't be too big of a pattern break. [EDIT]: I now added such a command, "sandwich".
Also, when I wrote the definition I thought of a theoretical implementation which can handle infinitely wide numbers. Because almsot the only usecase for stumble is to subtract, a value with infinitely many 1s will not persist because at infinity it overflows to a finite number once it is added to another finite number. And even if it persisted, a theoretical implementation with an infinitely wide stack could hold a number composed of infinitely many 1 bits (just as easily as a number composed of infinitely many 0 bits) and correctly overflow it to a finite number when needed. Lampe2020 --Lampe2020 (talk) 00:26, 2 May 2025 (UTC)
- Queueing is probably still possible with the from-the-top indexing that grille does, just a lot harder. Although indexing from the bottom could (if my tired brain isn't totally miscomputing right now) be made a lot easier without changing the behaviour of existing Stackowey programs by adding a command to push the stack size to the stack, so the programmer can subtract from that to go from the bottom of the stack upwards. But if you know and keep track of how many stack elements you add or remove after putting stuff in the queue you should already be able to (although quite inconveniently) handle a queue. And I added the prick command after-the-fact when I realized there is basically no good way to discard a stack element, so adding another command for pushing the stack size to the stack (also a way to reliably get random numbers by copying a number from the (stacksize+1):th place in the stack) wouldn't be too big of a pattern break. [EDIT]: I now added such a command, "sandwich".