High Rise
High Rise is a general class of esoteric programming languages described by User:ais523 in 2018, in an effort to find a Turing-complete language which would allow for the shortest possible implementation in a Turing tarpit (and possibly to aid in Turing-completeness proofs of languages with very small feature sets). One specific goal was to find an interpreter for a Turing-complete language in The Waterfall Model, using only a small number of waterclocks.
It is related to Collatz functions in a different way from Tip: instead of removing the addition, it removes the multiplication. This modification would normally mean that the program has access to only finite amounts of memory; High Rise solves this problem via allowing the program itself to change over time, describing a program with more and more memory as it does so, via the use of a non-fixed transition table.
Generalized High Rise
A generalized High Rise state consists of a data value, which is a nonnegative integer, and a transition table, which consists of some number of infinite sequences of nonnegative integers. (These sequences are numbered with consecutive integers starting from 0, i.e. if there are three sequences in the transition table, they will be identified as sequence 0, sequence 1, and sequence 2.) A generalized High Rise program simply specifies the initial state.
Execution of the program consists of repeatedly performing the following steps:
- Divide the data value in-place by the number of sequences, using integer division (e.g. if there are three sequences and the old data value was 10, the new data value will become floor(10÷3), i.e. 3).
- Delete the first element of sequence n and increase the data value by the deleted element, where n is the remainder of the division in the previous step.
These steps are repeated indefinitely forever.
High Rise languages
A High Rise language is a language whose programs are a subset of generalized High Rise programs. For example, "High Rise with two sequences, where sequence 0 is made of infinitely many zeroes and sequence 1 is a geometric progression" would be an example of a High Rise language.
Some examples of restrictions that ais523 considers potentially interesting are:
- Fixed transition table size
- The size of the transition table is something that seems appealing to minimize. Having just two sequences seems to be enough to produce a Turing-complete transition table. However, increasing the number of sequences to 3 or even 4 makes High Rise programs easier to write, and may allow the use of considerably simpler sequences.
- Only one nontrivial sequence
- The reason to use sequences, rather than fixed numbers, is to give the High Rise program access to unbounded memory (as it's not possible for the data value to become higher than twice the highest value in any of the sequences; the language is quite usable as a bounded-storage machine with only constant sequences, though). However, there's no reason why more than one non-constant sequence would be needed, and thus High Rise languages can reasonably restrict all but one sequence to be constant. (Most attempted implementations of High Rise can handle arbitrary constant sequences at no additional cost, but requiring all but one sequence to be constant zero is an obvious extension, and probably equivalent in the case where there are only two sequences.)
- Banning carries in the addition
- Numbers can be viewed (and perhaps implemented) as a string of digits, in which case carries from one digit to the next can be hard to implement. For example, some High Rise-like languages on two sequences may find it easier to use XOR than addition; if sequence 0 is a constant sequence, this could be fit into the generalized High Rise structure via duplicating sequence 0 as sequence 2, and changing the numbers from binary to ternary (i.e. if a number had a particular sequence of digits in binary in the original, it would now have the same sequence of digits in ternary in the updated program). This still gives 1+1=2, but now 2 and 0 are being treated as equivalent digits, so (as long as there weren't three XORs onto the same digit) the addition in the new language would effectively simulate XOR in the original language.
- Restricting to geometric sequences
- Arbitrary infinite sequences are often impossible to even specify precisely, let alone implement, so some restrictions are needed to make High Rise easily implementable in a low-level esoteric language. The most obvious restriction for compatibility with The Waterfall Model, and one that works well for High Rise programming in practice, is to restrict to geometric sequences (i.e. each element is a fixed multiple of the element before); this sort of sequence is very easy to generate within a counter machine (via loops which move a value back and forth via "destructive multiplication").
- Restricting to exponential sequences
- An alternative to a geometric sequence is a sequence of the form a·220, a·221, a·222, a·223… (possibly omitting the first few elements); this sort of sequence is intended for compatibility with Along and Across with a finite-state "along" language.
- Restricting to sequences of a form specified above, plus a constant offset
- Adding a constant offset to a sequence is effectively free when using counter machines. So, for example, a geometric sequence plus a constant offset is something that could reasonably be implemented in a counter machine, and could potentially add additional expressive power to the language.
- Interleaving sequences
- Instead of requiring a sequence to be a single geometric/exponential sequence, another possibility is to interleave multiple such sequences. Because generating a geometric sequence on a counter machine typically requires copying a value back and forth between two counters, it's often just as easy to produce two interleaved geometric sequences (which share a ratio between each element and the next), as it would be to generate just a single sequence. This sort of interleaving is also often easy to implement in other languages, and may be necessary for Turing-completeness if the other restrictions on the language are sufficiently harsh.
Implementations
Jelly
Here's an implementation of interleaved-geometric High Rise in Jelly:
®L ṛ®Ṅṙ€1$×⁴$$⁸¦©⁸ị0ị×¢ ⁵©ṛ³µṄ%1£‘Ç+:1£µ¹¿
(You can run this implementation online at Try it online!.)
This is a full program which takes the initial data value as its first command-line argument, the multiplier of the geometric sequences as its second (note: this is shared among all sequences, and applies per-element of the resulting sequence in the case of interleaved sequences, not per-element of the original sequences), and the various sequences to interleave as its third (each of which is specified as a list of the first elements of each of the interleaved sequences). Despite its appearance, the program is intended to be readable (!) rather than golfed (it's just that Jelly always looks like that).
Computational class
Some High Rise languages are known to be Turing complete; others have an unknown computational class. If you have any computational class results for interesting High Rise languages, please add them below.
XOR High Rise
An example of a Turing complete High Rise language is the language which accepts three sequences, with sequence 0 being constant zero, sequence 1 being interleaved exponential (geometric also works), and sequence 2 being constant zero, with addition never carrying. (We can call this "XOR High Rise", because it's effectively using XOR rather than addition.) This language can encode a cyclic tag system. Each production of the cyclic tag system is encoded into a string of ternary digits, using 10 to represent cyclic tag's 0, and 110 to represent cyclic tag's 1; and that is in turn encoded into a exponential/geometric sequence by using the encoded number with a large number of trailing zeroes (increasing in a geometric or exponential way, and sufficiently large to avoid any unintended collisions between digits; it's always possible to pick a sufficiently large number). Two copies of each of the sequences are made, with the second copy of each having terms one third as great as in the first copy. Then all these sequences are interleaved. Meanwhile, the data value represents the cyclic tag program's data string, using a different encoding: 11 to represent cyclic tag's 0, 121 to represent cyclic tag's 1, and any number of padding 0 and 2 digits being allowed between these.
The only thing that consumes digits from sequence 1 will be a 1 digit reaching the end of the data string (which is repeatedly shifted in the less-significant direction, as required by the definition of High Rise). Once this happens, there will always be another 1 digit arriving on either the next step, or the step after. In the cases of two 1s in a row (which, if we want to emulate a cyclic tag system, should do nothing but move to the next production, i.e. delete two elements from sequence 1), we'll end up adding a number made of 0 and 1 digits to the data value, dividing it by 3, and then adding one third of the initially added number; this is equivalent to adding the same number twice then dividing by 3, so the added number will be made of only 0 and 2 digits, all of which will be treated as ignored padding (and the added 2s don't disturb anything else because even the smallest had a higher place value than the entire data value had before the addition). On the other hand, if there were a gap between the two arriving 1 digits, the first sequence will have been divided by 3 twice rather than once, so we're effectively adding not twice the second number, but 1⅓ times the second number (i.e. 4/3 of it, or a shifted version of 4 times the number). 4 times 1 is (in ternary) 11, and 4 times 11 is 121, thus we convert the production encoding into the data encoding and append it to the data string (with some 0-padding in between), as required.