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).
Implementations
5-symbol tag system
Any Spiral Rise program defined on its four integers d, m, n, a, with a divisible by d, and that does not start in a halting state can be compiled into a tag system with modulus d:
| Symbol | Production |
|---|---|
N |
d copies of n
|
n |
N
|
a |
d-1 copies of A, then Z
|
A |
d copies of a
|
Z |
d copies of N, followed by md copies of a
|
The initial string is n-(d-1) copies of N followed by a copies of a. The basic idea is that the tag system queue alternates between two formats. One format (in which the initial queue starts) consists of n-p copies of N and da copies of a, in any order as long as a block of d as is not broken up (here, p, the tag system's "position", is 0 if the previous symbol was produced from, 1 if the symbol before that was produced from, 2 if the symbol before that was produced from, etc.). The other format consists of dn copies of n and a copies of (d-1 copies of A, then Z), again in any order (as long as neither a block of d Ns nor a block of (d-1 copies of A, then Z) is broken up).
When in the N/a format, the tag system does a divmod operation: every dth N gets produced from, and any Ns that remain after dividing by d instead affect the tag system's position (thus, although n is conceptually a quotient plus a remainder, thus two halves are stored separately, the quotient in the number of Ns/groups of d ns and the remainder in the position p); and as Spiral Rise requires, the quotient and remainder are added before doing the divmod (because a nonzero p means that fewer Ns are needed before reaching the first produced-from block.)
When in the n/A/Z format, everything is made out of d-sized blocks, so the position stays constant relative to the d-sized blocks; if p is 0, then the ns and Zs are produced from, otherwise the ns and As are produced from. In the latter case, the queue is changed back to the other format but with no other changes; in the former case, a is multiplied by m and n is increased by the old value of a, as the Zs expand. (The queue ends up with the representations of n and a mixed together in an arbitrary sequence, but the construction is designed so that this does not mater.)
One potential issue with this construction is that the halt states do not match up correctly; Spiral Rise's "natural" halt state, in which n becomes less than d, does not halt the tag system (instead it will enter a "tight infinite loop" in which the same queue sequence repeats over and over again). It is possible to change one of the as in the produce of A to a halt symbol, which would implement a variant of Spiral Rise which halts upon (and only upon) seeing a particular nonzero remainder; this variant is probably strongly Turing-complete, although this has not yet been proven.
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