Talk:Something?Oops!

Computational class

What happens if you attempt to assign a negative number to ,? If the answer is "the code continues running from the first line" (i.e. the instruction pointer runs from "behind the program" until it finds some commands to run, setting its value to 0 in the process), I'm not 100% convinced it's an FSM, as reading variables which are (negatively) unbounded might then be possible. It'd likely be Turing-complete if it had a third variable that can be read or written without computational class side effects (producing output isn't a side effect that impacts the computational class, so you could use . as a normal variable if you really had to). With only two, it's a pretty interesting computational class problem (it's likely to be somewhere in the range from a one-counter machine to TC). --ais523 18:24, 10 July 2018 (UTC)

After thinking about this some more, the language is probably a PDA (assuming goto-negative is allowed). Multiplications are trivial to manage without loops (just use repeated addition), and divmod, although it requires a loop, doesn't require you to remember where in the program you were (you can store it in the modulus by adding it to the value you're divmodding, assuming you know it only has a certain possible range), so you can start off the program by just doing a divmod by a fixed value and branching to one of several lines based on the modulus (S?O!'s semantics happens to do this naturally!). The basic problem here is that the divisor is fixed (we're already using our two writable variables to handle the dividend and the quotient), meaning that we can only pop digits from the least significant end of the number. The only "obvious" push routine is a multiply-add, which would push to the least significant end, effectively giving us a "one stack" construction (thus a PDA). However, there's one potential loophole here (you can multiply by numbers other than the base); is that enough to squeeze a bit of extra computational power out of the language? --ais523 20:18, 10 July 2018 (UTC)

Oh, duh: you can do something like storing two counters as -2^a3^b, and have the divmod mod 6. That way you can divmod the components individually via doubling or tripling the number (as appropriate) before you start the calculation.

The full design, then, would be as follows: out of the two variables that have full read/write behaviour, one of them stores two counters in the above-mentioned form, and the other as a temporary. You can multiply the "main variable" by a constant via copying it to the temporary (i.e. the temporary = the main variable + 0), then repeatedly adding the temporary to it. In order to do a divmod of the main variable by 2 or 3, you first multiply the main variable by 3 or 2 respectively, then multiply it by a large value x, add a constant (to determine which lines are returned to), copy that into the temporary, zero the main variable, and goto the temporary; the first couple of lines of the program will subtract one from the main variable and goto the temporary + 6x. So by the time the temporary finally becomes positive, the main variable will hold the quotient of the divmod, and the remainder will determine which line we end up on (we'll end up on one of two or three possible lines based on the remainder, and where those lines are will depend on the added constant). This bootstraps correctly (we can put initialisation code on line 6x, which needn't be used for anything else), and thus if the language allows negative IPs (and just allows them to run through to zero), it's actually Turing complete. --ais523 20:56, 10 July 2018 (UTC)