Spiral Rise
Spiral Rise is an esoteric programming language created by User:ais523 in 2020, heavily inspired by High Rise. Its main purpose is to allow for very small implementations in counter machines, while remaining Turing complete; the state of a running program can be stored using only two numbers, and the program itself using a further two numbers, with all the operations in the language being easy to implement on a typical counter machine.
Semantics
The state of a running Spiral Rise program consists of four nonnegative integers: the divisor (d) and multiplier (m), which remain fixed for the lifetime of the program, and the number (n) and addend (a), unbounded nonnegative integers which can change as the program runs. A program is specified via specifying its initial state.
To perform one step of a Spiral Rise program's execution, do the following:
- If the number is less than the divisor, the program's execution must halt. If the number is less than the 4 times the divisor, it is unspecified whether or not the program's execution halts. Otherwise, the program does not halt this step.
- Divide the number by the divisor, producing a quotient and remainder.
- Set the number to equal the quotient plus the remainder.
- If the remainder is 0, then alter the number by adding the addend, then alter the addend by multiplying it by the multiplier.
The program is executed by repeatedly running steps until it halts.
Here's what an implementation could look like in C-like pseudocode:
while (n >= d) { /* test could also be n >= 4 * d */
bignum q = n / d;
bignum r = n % d;
n = q + r;
if (!r) {
n += a;
a *= m;
}
}
Computational class
Spiral Rise is believed to be able to more or less directly implement a tag system (regardless of the value of the tag system's m, i.e. this is not limited to 2-tag; to avoid confusion between the different uses of m in the tag system and in Spiral Rise, the tag system's m will be called s in this section).
The basic idea is to choose d as 2s+1, and to ensure that almost every base-d digit in a is either "0" or "s-1" (the only exception is a "2" in the most significant position). To ensure that a keeps this property, m should be a power of d. Also, the least significant digit of n should initially be an even number.
The repeated "divmod, then add the quotient and remainder" operation that powers Spiral Rise effectively forms a running digital root. In particular, both "0" digits and "d-1" digits in n have no permanent effect on the least significant digit as they shift into that location (just as neither "0" nor "9" has any effect on a digital root in base 10). A "d-1" digit will have a temporary effect, of reducing the least significant digit of n by 1 for one step, but because the digits that arrive in n from a are all even numbers ("0", "2", and "d-1" are all even), this will never cause the addend to be used, and thus these digits are basically always no-ops.
The computational power of the language comes from the occasional odd digit in n. This can happen when a is added to n more than once, and two of its "d-1" digits overlap with each other, adding together and causing a carry. The digital root of the combination will still be "d-1" (just as all multiples of 9 have a digital root of 9 in base 10), so again, there will be no permanent effects; however, the temporary effect will be to reduce the least significant digit of n by 2, rather than 1. This is capable of zeroing it and thus causing a use of the addend, but only if the digital root was 2 before the carry combination arrived.
This is where the significance of d being 2s+1 comes in. The "2" digit at the most significant end of a is the only way in the whole computation to get something that does not have a digital root of d-1, so each such digit will end up adjusting the digital root by 2. There are d-1 possible digital roots, as 0 is not a possibility if n starts indivisible by d, and thus only the even digital roots will end up being used. Assuming that it's never the case that four or more nonzero digits from a hit the same digit in n (or a carry resulting from this sort of addition), which is easy to arrange (via making m sufficiently large), digital roots other than 2 will entirely lock out the addend from any sort of use, as it will be impossible to ; a the least significant digit of n to 0 in that case. This means, in effect, that only every sth addend use is capable of producing any further addend uses (because every addend use places exactly one "2" digit into n, above its own output). This neatly models the requirement of tag systems that only every sth symbol may be used, and the others must be ignored.
The only remaining obstacle to proving Turing-completeness is to show that it's possible to use a and m to implement a lookup table. This should be fairly easy, using "pairs of collisions between different additions of the addend that cause a carry" as symbols, but has not yet been proven (although Spiral Rise's author is almost certain that the language is indeed Turing complete).
Comparison with High Rise
Spiral Rise is, for the most part, very similar to High Rise. The only thing that prevents it being a High Rise language (specifically, the High Rise language with the "0" sequence geometric and the others constant-zero) is that the remainder of the division is kept and added to n, rather than being discarded. This minor tweak to the language ends up solving two problems at once.
One of these issues is that in High Rise, it is complex to store enough state to allow parts of a High Rise program to do different things in different contexts. Normally, you have to make use of a somewhat irregular sequence to accomplish this (e.g. XOR High Rise uses an interleaved sequence for the purpose of using the location within the interleaving as a kind of simplistic state machine). While this is certainly possible, it tends to add complexity to implementations of Turing-complete High Rise languages, increasing their minimum size. Spiral Rise can make use of the remainder, which is preserved between divisions, as an additional piece of state (as seen in the discussion in the previous section).
The other issue is that using large divisors in a division or modulus implementation in a small counter machine generally requires the use of a counter to store the remainder of the running division, because otherwise you would need to allocate one state to each possible value of the remainder. However, this causes control-flow complexity in its own right, because you need to clear the remainder counter in between divisions; this means that the same counter is used for two different purposes, something which tends to cause the size of simple counter machine languages to explode. This is unfortunate, given that division and modulus operations are by far the simplest way to create data structures like stacks on a counter machine. Spiral Rise solves this problem by allowing implementations to simply not clear the counter; the effect of this is that the value that's "stuck in the counter", the remainder, effectively adds to the dividend of the next division/modulus operation, which is exactly what Spiral Rise requires. (In fact, this observation is what lead to the creation of the language, and the use of the remainder as additional state was a fortunate extra benefit.)
Implementations
The Waterfall Model
Any Spiral Rise program defined on its four integers d, m, n, a, and that does not start in a halting state can be compiled into a program in The Waterfall Model using the following matrix:
| ? | 7 | 7 | 7 | 7 | 7 | 7 | 7 | Use as control / when value is small | Use as data / when value is large |
|---|---|---|---|---|---|---|---|---|---|
| n-d | 0 | 0 | 0 | 0 | 0 | 0 | 0 | Halting the program | Approximately proportional to n regardless of what else is happening |
| d+1 | d | d+1 | d+1 | -d-1 | 0 | -2 | -1 | Handling the end of a step | Temporary storage for n during division |
| d+1 | -d | -d-1 | 0 | 0 | 0 | 2 | 1 | Retrieving n from temporary storage after division | Temporary storage for a during addition |
| a(d+1) | -d-2 | -d-2 | -d-2 | d | -1 | 1 | 0 | Rearranging control flow after a is multiplied by m | Main storage for a |
| d | 2d+1 | 2d+1 | d | d | d | -d | 0 | Dividing n by d | Remembering the remainder of the division |
| n | d+1 | d+1 | m(d+1) | -d-1 | 0 | 0 | 0 | Multiplying a by m, and adding it to n | Handling the comparison of the remainder against 0 |
| n | 0 | 0 | -d-1 | d+1 | 0 | 0 | 0 | Retrieving a from temporary storage after addition; also triggering the end of a step | Main storage for n |
To convert this matrix into a real program in The Waterfall Model:
- substitute variables;
- add a constant to each zeroing trigger so that it's entirely nonnegative;
- multiply all zeroing triggers and initial values by the number of rows, then add 0 to the initial value of the first waterclock, 1 to the initial value of the second, and so on (this causes the zeroing trigger that appears earlier in the program to be the one that runs if two would otherwise zero simultaneously); and
- set the maximum value in the top-left corner appropriately.
As with most heavily golfed programs, the above program can be quite hard to understand, as most waterclocks are used for multiple purposes (typically data storage while their value is high, and control flow while their value is low). Some comments (not part of the program) have been added to give a little insight into what is going on.
The above program was compiled (by hand) from the following Waterfall Construction Kit program, which might or might not give some insight into how it works:
# constants used: D = ?. # divisor M = ?. # multiplier N = ?. # initial n A = ?. # initial a # Variables used: n := N. # number q := 1. # quotient r := 0 max D. # remainder, virtually part of n a := A. # addend b := 1. # temporary to hold addend during addition # Highest priority trigger first. ## a halt condition would go here, but the one in the table above was written directly, not compiled # Sloppy triggers (all but one condition precise, default trigger does not change values) q <= 0 :- q += 1, a -= 1*,b += 1, n -= 1. # reset after q copied to n after b->a shift b <= 0 :- q -= 1, n += 1. # after b->a shift, copy q back to n a <= 0 :- r += 1, a += 1, b -= 1, q -= 1. # after a->b shift, shift back the other way # Precise triggers (only one condition; precise and gets tighter upon running the default trigger) r >= D :- r -= D, q += 1. # if the remainder gets too large, bump quotient 2 * n + r <= 0 :- a -= 1, b += M, q += 1. # after dividing, 0 remainder -> add a to q, multiply a by M n <= 0 :- b -= 1, a += 1. # then unconditionally copy b back to a # Default trigger (no conditions, changes at least one bounded value) :- n -= 1, r += 1. # continue dividing the number