DownRight
DownRight is an esoteric programming language created by User:ais523 in 2010, although the details of the syntax were not finished until 2011.
Semantics
A DownRight program is a two-dimensional matrix of possibly empty strings, the instructions, where the alphabet for the strings consists of only two symbols, "down" and "right". Program execution uses nothing but the program (which never changes), the instruction pointer (starting out at the first, i.e. top-left, cell) and one queue (the only place data is stored), which also contains only "down" and "right" (single symbols this time, not strings). The queue starts out initialised with the contents of the first cell. Program execution proceeds by repeatedly removing symbols from the front of the queue and moving the instruction pointer down or right according to the symbol removed (wrapping both vertically and horizontally, treating the program as a torus). Whenever the IP moves onto an instruction, it is pushed character-by-character onto the back of the queue. If the queue is empty when an attempt is made to remove a symbol from it, the program halts.
In DownRight programs themselves, the width and height of the program must be co-prime. (An extension of the language without this restriction is easy to imagine, and many interpreters are likely to be able to interpret this extended version too. However, removing the restriction makes the language substantially harder to compile into several languages, because with the restriction, one number can easily be used to represent both coordinates.)
Syntax
(Much of the syntax is due to User:Vorpal.) Each string in a DownRight program is notated as a non-empty sequence of characters that contains no whitespace; all characters but ↓ and → are treated as comments and ignored, with ↓ and → being treated as the "down" and "right" symbols respectively. (When notating an empty string, at least one comment character must be used, so as to make the character sequence non-empty.) These are written in sequence, with rows written top-to-bottom and strings written left-to-right within a row; strings in a row must be separated with sequences of horizontal whitespace (spaces and horizontal tabs), and rows themselves must be separated by sequences of whitespace that contain at least one vertical whitespace character (newline, formfeed, or vertical tab). Trailing whitespace on the program is ignored; apart from that, a program is a syntax error if each row does not have exactly the same number of columns, or if the number of rows and the number of columns are not coprime.
Computational class
DownRight is Turing complete. The proof below by User:ais523 (2010) was the one that originally showed the Turing-completeness of the language.
The easiest way to show this is probably via the following algorithm to compile tag systems with no halt symbol (which are nonetheless Turing complete despite not having one, as they halt when their queue gets too short) into DownRight:
- Add an otherwise unused symbol to the tag system whose production rule produces itself, then m-2 arbitrary symbols, then the initial word (effectively, transform the tag system into one where the initial word is a single symbol long); call this symbol S
- Add unused symbols to the tag system until there are at least 5 symbols, and a prime number of them (call this number p) that is not a factor of m; their production rules are irrelevant
- Find another prime q that is neither equal to m nor p
- Assign an integer from 0 to p-1 inclusive to each symbol, with S being numbered 0
- For each word in a production rule, encode it into a DownRight string as follows: for each symbol in the word, take the corresponding number n, and convert it to a substring consisting of a right symbol, then n down symbols, then q-1 right symbols, then (p-n) down symbols; as an exception, the word encoding the production rule for S should omit its first right symbol
- Make the program p rows high and qm columns wide; the production rule for each symbol should go at coordinates (0 from the left, n from the top), where n is the number that corresponds to that symbol, and every other string should be empty
The way this works is by mapping the tag system queue to the DownRight queue (using the same encoding as was used to encode the production rules); every mth symbol will cross the first column (as each symbol moves exactly q spaces to the right, and the program is qm columns wide), and so just as in a tag system, all but every mth symbol will be disregarded and have no effect (with each symbol moving a total of p rows downwards, and so leaving the program at the same vertical height). The location where that column is crossed will depend on the symbol, and cross at the row corresponding to the symbol, so what is added to the queue will be the encoding of the appropriate production rule, again just as in a tag system. Finally, p must be coprime with qm, as it is prime and not a factor of q nor m (by definition).
Simpler proof
- Note that this proof uses
vand>for down and right symbols. They may be replaced with the actual DownRight arrows.
Here's User:Keymaker's alternative proof (2025) of DownRight's Turing-completeness, via Cyclic Tag translation:
Creating the construction will demand only a few simple calculations, which for many people are simple to calculate in their minds. The most complicated procedure is multiplying an arbitrary (but relatively small) positive integer by two, which is a process easily done without thinking; for example by collecting n number of white stones in a bowl, where n is the number that is to be doubled. Then, take every white stone from the bowl one by one until none are left, and whenever taking a white stone, place two black stones into the bowl. After all white stones are gone, there will be 2*n black stones.
The height of the matrix is the number of production rules in the Cyclic Tag program multiplied by two. The width of the matrix is the aforementioned value increased by one. Because any n and n+1 (assuming n is 1 or larger) are co-prime, the matrix fulfils DownRight's co-primality requirement for the matrix dimensions. (Simply add one black stone into the bowl containing the height, to get the width.)
Now that the matrix dimensions are set, it can be filled.
At index 1,1 (the top-left corner) there is the cell whose data initializes the queue at the start of a DownRight program. Therein is placed the short sequence ">v" (which moves the pointer to 2,2) followed by the initial queue in its encoded form.
The encoding for 0 and 1 is, throughout this translation, this: Replace every 0 with "vv" and 1 with n ">" arrows, where n is the width of the matrix, followed by "vv". So, for example, in a matrix where width is 7, this construction would be >>>>>>>vv for 1. (0 is "vv" regardless of width or height.) Initial queue data "1001" would be >>>>>>>vvvvvv>>>>>>>vv in this example. Do not forget to add the ">v" before the initial queue that is placed at index 1,1 (making the complete 1,1 string >v>>>>>>>vvvvvv>>>>>>>vv in this case).
Go through every production rule of the Cyclic Tag program and start at index 1,2 (x=1, y=2). Take the production rule, such as "101;". Remove the ";", replace each digit with the corresponding construction mentioned above. (For an empty production rule the resulting string is an empty string.) For a matrix with its width as 7 (as in above example), the string would be >>>>>>>vvvv>>>>>>>vv (1 0 1). It is placed at index 1,2. Then increase the y location by two and do the same procedure for the next production rule, for as long as there are them (if there are more than one). They are placed at (1,4), (1,6), and so forth. Once each is set, the translation is complete.
Languages/systems that translate into DownRight
Tag system into DownRight
Cyclic Tag into DownRight
Minsky Machine into DownRight
User:Keymaker has created two Minsky machine translations, the first in 2018 and the improved one in 2019 (but they were not published until 2025). The first uses 2-register MM and stores the two registers as a multiple of primes 2 and 3. The second translation can feature any number of registers and stores each register on its own, in 2^n units of "vvvv". Following the execution of the program is much easier, too.
Miserie into DownRight
Miserie is a minimal state and queue language designed specifically for DownRight translation. Because of some errors in User:Keymaker's thinking, the translation took much longer than expected (and was the reason the Minsky Machine translations were not published earlier). What is notable in this translation is that it operates a binary queue construction within the DownRight queue alongside data used for arbitrary state control. The memory usage is horrific as is the execution speed! Miserie itself is quite capable; for instance, there exists an I/D machine to Miserie translation. (However, with present implementations running any I/D machine to Miserie to DownRight construction is more or less impossible.)
DownRight into Cyclic Tag
This small aside by User:ais523 may not have been seen widely enough:
- Also interesting is that DownRight compiles quite easily into cyclic tag (for a DownRight program x columns wide and y rows high, map the cell at (a from the left, b from the top) to the (ya+xb)th production rule (modulo xy), with production rules encoded as (y-1) 0s then a 1 for a down symbol, and (x-1) 0s then a 1 for a right symbol.)
This means that anything translated into DownRight can be translated into Cyclic Tag quite efficiently.
Translation example
TODO: Example, preferably with some kind of informative graphics that exhibits the relationship between the two systems.
Note on a future interpreter
What is needed in a future interpreter is optimization of steps. An interpreter like dori2.py optimizes memory usage (although that, too, could be made faster with more advanced programming techniques and implementation in C), but it has no optimization on executing instructions. Some ideas might be:
- Place any good ideas here!
Implementations and relevant software
- Two early implementations can be found on the talk page.
- http://yiap.nfshost.com/esoteric/downright/dori2.py - dori2, a memory-optimizing interpreter (uses the simplified input format, or a matrix that uses "v" and ">" characters (for technical reasons))
- http://yiap.nfshost.com/esoteric/downright/drintgen.py - drintgen, for creating a html/Javascript interpreter of a given DownRight program, which can be run and inspected in browser (uses the simplified input format)