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 intepret 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 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).

It seems likely that other simple systems compile in a similarly simple way into DownRight, particularly cyclic tag. (It seems likely Minsky machines do too, but this is harder to visualise, and thus to prove.) 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.)

Implementations

• Two implementations are on the talk page.