Talk:Addpocalypse

Computational class

This is sub-TC at the moment. An equivalent view of the language is to imagine that "0+" instead decrements all registers except #0, and register #0 is thus always 0 (which is clearly equivalent to the current definition). Then, because "n?" restarts the program if #n is not equal to 0, in any case where the program continues then register n will have a known value for the rest of the program. This means, among other things, that there's never any point in testing the same register twice in the program, so we can assume that any program that might demonstrate TCness tests each register once. Then, imagine renumbering the registers in the order that they're tested (so that 1? comes before 2? comes before 3?, etc.) – this means that it's impossible for the value of a higher-numbered register (other than its zeroness/non-zeroness) to affect the value of a lower-numbered register, and that in turn makes it impossible for the language to retrieve an arbitrary amount of data (because data has to be retrieved into a register with a higher number and once it reaches the highest-numbered register, it can't be retrieved any more).

The language would be more powerful if the n? instruction were reversed (i.e. to jump to the start if the values were the same, rather than if they were different), although it would probably be harder to write in. I think that's probably enough to make it TC, via using a separate register to remember which register you just tested – I'm not 100% sure though because I haven't yet figured out how to start up the program in the desired state. --ais523 15:40, 16 May 2024 (UTC)