Conedy
Conedy is a simplification / tarpitification of Trajedy, created in 2017 by User:ais523. It's a two-dimensional language in which movement of the instruction pointer is the only data storage within the program; despite the bounded playfield, infinite storage is achievable by the fact that the instruction pointer can take on rational, rather than merely integral, coordinates.
Syntax
A Conedy program is a rectangular matrix of Unicode characters, each of which must either be a cased letter, or a space. (This matrix can be represented in a file via using newlines to separate the lines.) For each uppercase letter, there must be a corresponding lowercase letter (for which both letters case-fold to the same codepoint), and vice versa; each letter must therefore be unique in the program. Uppercase letters are called beacons, lowercase letters nets. The top left corner of the program must be a net.
Semantics
Think of each cell of the matrix as being a 1×1 square. A beacon occupies a single point at the centre of that square; a net occupies the entirety of the square it's in. The instruction pointer starts at the centre of the top-left cell.
Whenever the instruction pointer is in a net (including being on its boundary), including at the start of the program, it changes direction to start moving directly towards the corresponding beacon (this degenerates to a no-op if it's already moving in that direction). (Note that the instruction pointer will always have rational coordinates at this time; it starts at rational coordinates, thus will move in a direction with rational slope (towards a rational-coordinate'd beacon), thus will hit the edge of the next net at a rational coordinate, and so on.) Hitting the boundary of two nets simultaneously is undefined behaviour.
Moving the IP outside the matrix terminates the program.
I/O extension
Conedy can be extended to perform input and output by allowing duplicate letters to appear in the program (up to two copies of each letter, not unboundedly many copies). In the case of duplicate nets, the net sends execution towards the beacon as usual, but also produces one bit of output (a 0 bit if the net that was used appears first in the normal left-to-right, top-to-bottom reading order, a 1 bit for the other net). In the case of duplicate beacons, one bit of input is read and used to determine which beacon to direct execution to, in the same way.
Computational class
Implementing data storage in Conedy can be done via using only the fractional part of the x coordinate (and the top and bottom edges of nets), using the integer part like a more typical instruction pointer. By allowing execution to aim towards a beacon, but stop short of it (due to a net being in the way), you can divide the fractional part of the x coordinate by a rational number (greater than 1) of your choice, and add a constant at the same time. If you allow execution to pass a beacon and then hit a net well beyond it, you can instead multiply the x coordinate by a rational number of your choice. It's also possible to add arbitrary integral values to the x coordinates, without interfering with the fractional part (other than subtracting it from 1) via sending it from one net, through a beacon, to another net that's rotationally symmetric with the original net around the beacon; this technique makes it possible to keep the y coordinate under control. Finally, after multiplying the x coordinate via the earlier technique, a row of nets can be used to split control flow based on the new integer part of the coordinate.
In other words, we can effectively implement a language with the following commands:
- x := (x + j)/k (for integer j, k, 0≤j<k)
- x := fractional part of kx; goto one of k commands based on the integer part of kx
It's unclear whether this is enough to make the language Turing complete. It is enough to implement any push-down automaton, via treating x as a list of digits and "pushing" and "popping" from the most significant end. However, there are some Conedy programs that cannot be implemented on a push-down automaton (meaning that it must be in a strictly more powerful computational class). For example, "input a number n in unary, followed by a 0, then a list of binary digits, and output which of those digits match the corresponding digits in the binary expansion of 3-n" is easy to implement in Conedy, but Ogden's lemma shows that a PDA is insufficiently powerful to implement this (by marking elements of the initial unary string).
Implemenation
- Conedy interpreter in Python created to investigate the computational class.