Trianguish
Trianguish is an esoteric programming language created by Radvylf in 2022. It is almost a cellular automaton, but has additional features such as I/O support and random number generation.
Specification
Trianguish programs exist on an infinite triangular tiling (although all but finitely many cells of the grid are blank); the triangles are equilateral, and oriented so that one of the sides is horizontal. Each cell of the grid, known as an "op", stores two pieces of information: the "pin value", which is either an integer from 0 to 215 inclusive or the special value NIL; and the "ID", which specifies one of 16 different commands, and also which side each of that command's arguments ("pins") are connected to. (Commands can therefore exist in 1, 3 or 6 different orientations, depending on how symmetrical they are with respect to their pins.)
Execution consists of alternating between two operations forever (or until the program enters a tight infinite loop, defined as a state in which no input or output occurs and no changes to ops' values or IDs occur:
- Pin value updates: each op's pin value is updated based primarily on the pin values that adjacent ops had on the previous cycle;
- Building: if there are any active builders on the grid, they change the ID of adjacent ops (making Trianguish a self-modifying language). In the reference implementation, building on an op also changes its pin value to NIL, but this may be a bug rather than an official part of the language.
For most commands, an op with that command will have one or more sides designated as output pins. It is impossible to read a op's pin value except through its output pins. When an op is said to "read via" a particular pin, it means that its behaviour is based on the pin value of the op that's adjacent on the side of that pin (all commands run simultaneously, so it sees the value of that op before the current cycle's updates); or if that op does not have an output pin on its side adjacent to this op, this op behaves as though it read NIL instead (because it cannot read the pin value in this situation).
Trianguish is represented graphically; a command is drawn as three colored lines connecting the centre of the op to the midpoints of its edges. A command is defined by which colors of lines exist (and its orientation by which color connects to which edge); sometimes more than one command uses the same set of colors, in which case a character is placed on the op to disambiguate (or in the case of builders, a line between two of the pins). Here are the commands:
- No-op (A=gray, B=gray, C=gray) [0]
- This command always has a pin value of NIL (although it has no output pins, so this value cannot be read anyway).
- Zero (A=blue, B=blue, C=blue with
0) [18] - This command has three output pins, and always has the pin value 0.
- One (A=blue, B=blue, C=blue with
1) [24] - This command has three output pins, and always has the pin value 1.
- Minus one (A=blue, B=blue, C=blue with
-) [30] - This command has three output pins, and always has the pin value 215/-1 (pin values are calculated modulo 216, so these are equivalent).
- Wire (A=green, B=gray, C=blue) [36]
- This command changes its pin value to match a value read from the green pin. The blue pin is an output pin.
- Split wire (A=green, B=blue, C=blue) [54]
- This command changes its pin value to match a value read from the green pin. Both blue pins are output pins.
- Logical AND (A=green, B=purple, C=blue with
T) [72] - This command reads a value through the green and purple pins; if either is NIL, its pin value becomes NIL, else it changes to match the value read via the green pin. The blue pin is an output pin.
- Logical OR (A=green, B=purple, C=blue with
S) [90] - This command reads a value through the green and purple pins; it changes to match the value read via the green pin if that is not NIL, or via the purple pin if that is not NIL, or otherwise becomes NIL. The blue pin is an output pin.
- Excluding wire (A=green, B=purple, C=blue with
N) [108] - This command reads a value through the green and purple pins; it changes to match the value read via the green pin unless the purple pin has the same value, in which case it becomes NIL. The blue pin is an output pin.
- Adder (A=green, B=green, C=blue with
+) [126] - This command adds the values read through the green pins (mod 216), and changes its value to match, or to NIL if either of them were NIL. The blue pin is an output pin.
- Multiplier (A=green, B=green, C=blue with
×) [144] - This command multiplies the values read through the green pins, and changes its value to match, or to NIL if either of them were NIL. The blue pin is an output pin.
- Comparator (A=green, B=purple, C=blue with
C) [162] - This command subtracts the value read through the purple pin from the value read through the green pin, and changes its value to match the sign of the result (215/-1 if negative, 0 if zero, 1 if positive). The blue pin is an output pin.
- I/O command (A=green, B=purple, C=blue with
I) [180] - This command outputs any non-NIL value read through the green pin. If the purple pin is non-NIL, it reads a value from input and changes its pin value to match; otherwise, its pin value becomes NIL. The blue pin is an output pin.
- I-Builder (A=brown, B=green, C=blue, line connecting brown to green) [198]
- During value calculation, this command changes its pin value to match a value read from the green pin, and the blue pin is an output pin.
- During building, this command changes the ID of the op connected via the green pin based on the builder's pin value, unless the builder's pin value is NIL.
- O-Builder (A=brown, B=blue, C=green, line connecting brown to blue) [204]
- During value calculation, this command changes its pin value to match a value read from the green pin, and the blue pin is an output pin.
- During building, this command changes the ID of the op connected via the blue pin based on the builder's pin value, unless the builder's pin value is NIL.
- S-Builder (A=brown, B=gray, C=blue, line connecting brown to gray) [210]
- During value calculation, this command changes its pin value to match the ID (not value) of the op connected via the gray pin.
- During building, this command changes the ID of the op connected via the gray pin based on the builder's pin value, unless the builder's pin value is NIL.
Builders can translate between pin values and commands (because they change a pin value based on an ID or vice versa). Thinking of the three sides of a triangular op as being in the directions /, - and \ (regardless of whether the triangle is pointing up or down), it is possible to calculate an orientation value from 0 to 5 based on how the pins of the op match the pin colors in the order listed above:
/ | \ orientation of the pin from the centre to the side of the triangle \ - / orientation of the triangle side itself 0 A B C 1 C B A 2 B C A 3 B A C 4 C A B 5 A C B
The translation between an ID and pin value is then done by adding a number representing the command (listed above) to the number representing its orientation. Some commands are symmetrical, but seem to internally have an orientation anyway, meaning that, e.g., the ID for a "zero" command could be 18, but could also be, e.g., 22 (depending on which of the three blue wires is considered to be which).
Building nonexistent commands is allowed (and their IDs can be read back as a pin value via using an S-builder, round-tripping correctly). With default settings, the reference interpreter defines their behaviour by repeatedly subtracting 6 from the ID until a valid command is reached, and then behaving like that command.
In most cases, commands are defined in such a way that the order in which they run within a cycle is irrelevant. There are two exceptions: I/O commands (which order do they output / input in?) and builders (if two builders build on the same cell, which one wins?). The language is defined to randomize in this situation, although the reference interpreter has some options to change this behaviour.
Computational class
Trianguish is pretty powerful in terms of what it can do with finite amounts of memory. For example, arbitrary constants can be produced by adding lots of ones together. As long as you don't mind a potentially large delay between the input and the output, it is possible to implement an arbitrary function from non-NIL values to values including NIL (with NIL mapping to NIL) in a range of different ways (a very inefficient but simple method is to use split wires to make a number of copies of the input equal to the number of input values that produce non-NIL outputs, use excluding wires to exclude 215 of the 216 possibilities from each wire so that each possible input value goes down a different wire, then use an adder to adjust each value to the desired output, using logical ORs to ensure that all the resulting values end up back in the same place). It is also possible to use circuitously routed wires to delay a signal by any sufficiently large even number of cycles. (Using wires, the delay must be even because the pin values move between an upwards- and downwards-pointing triangle, or vice versa, on very cycle. As it happens, odd delays are also possible via using S-builders, but this is not required for the computational class proof.)
By using multiple such functions, and combining the output with a logical OR, it is possible to create a function which, when it receives a non-NIL input, will produce a specified sequence of outputs, in a particular order, and with full control over the timing of each output modulo 6 (except that the parity of timing of each output depends on that of the input, but you can still choose 0/2/4 modulo 6 freely). In order to construct a Turing-complete language from this, it would be sufficient to have a set of six unbounded stacks, that work along the following principle: there is one input wire shared among all the stacks; the values of the stacks do not change as long as that input is NIL; for most non-NIL inputs, sending that input along the input wire pushes it onto one of the stacks (chosen based on the timing of the input modulo 6); for one specific non-NIL input (e.g. 215), sending that input along the input wire instead pops one of the stacks (again, chosen based on the timing of the input modulo 6); there is an output wire that can be used to read the popped values. This is enough power to implement Esimpl, without pushback instructions, with 3 stacks, and with a maximum of 215 stanzas (which is easily enough for Esimpl to be Turing-complete, e.g. UT19 uses fewer resources than this when compiled into Esimpl): the idea is to arrange the program something like this:
/------------>-- stack input (push/pop commands) | ROM ^ split--<--\ v | ROM | | | \-->--adder--<-- stack output (popped value)
in which the top ROM, upon receiving a stanza number, sends the sequence of push commands and the "pop" half of a pop-goto command to the stack input, and the bottom ROM, upon receiving a stanza number, sends the "goto" half of a pop-goto command towards the adder, so that it arrives at the same moment that the value popped from the stack does (and thus adds to the popped value in order to produce the number of the new stanza, as Esimpl requires). A goto command (as opposed to pop-goto) can be implemented by pushing 0 onto an arbitrarily chosen stack, and then doing a pop-goto on that stack.
Here's an example of how the infinite stacks can be implemented. The top part of the linked program is a finite section of a repeating pattern; this finite section implements six stacks that use the communication protocol listed above (using 215 as a "pop" command), but can each store only finitely many elements (in this case, four of them). Extending the pattern by adding additional copies would increase the number of elements that can be stored.
The idea behind the construction of the stacks is that the data is stored in the hexagons in the middle of the pattern: the six ops that make up the hexagons each store the value of one stack, with the top of the stack being on the left. When a value to be pushed onto the stack is received from the input, it is used to replace the appropriate value in the leftmost hexagon via being sent through the "strong" (green) side of a logical OR; it also passes along the wire at the top of the construction, activating the logical ANDs for one cycle each and allowing one non-NIL value to pass through (the value from the appropriate stack), which then arrives on the strong side of a logical OR and replaces the appropriate value in each non-leftmost hexagon with the correct value from the hexagon to its left. Because the paths between the hexagons are more circuitous than the path along the top, these paths will be storing the value from before the push (rather than afterwards), so each of the new values is based on the old value of the hexagon on the left, rather than the new value, simulating a stack push.
Pops work in much the same way; the difference is that, due to the arrangement of comparators and excluding wires, a value of 215 will be sent along the bottom rather than the top. This causes the values to move to the left in exactly the same way as a push moves them to the right (the bottom-most value on the stack becomes duplicated, but Esimpl programs can be and usually are written so that the stacks never empty, causing this duplication to be unobservable). In order to implement reading of the popped value, the value of the top of the stack is constantly output on the output wire; when using the Esimpl construction above, this will only actually be read when a table number is sent towards the adder (otherwise, the adder's left input is NIL and thus its right input will matter). "Pop and read the popped value" is thus implemented by reading the popped value before popping it.
Here's a demonstration of the stacks in action.
The bottom part of the linked program shows how to cause the stack to grow during runtime (and you can run that program to actually see how the stack grows). For demonstration purposes, this uses an I/O command to read a long sequence of IDs-converted-to-pin-values from the input; however, a full construction would generate this sequence arithmetically, place it into a very large loop of wire, and have the sequence repeat forever (rather than the two repeats used in the demonstration). The sequence is used to power a "universal constructor" that can build arbitrary Esimpl code. The universal constructor consists of two parts: a wire that goes to the right and stores the sequence (sent at the rate of 1 per 3 cycles), at the top of the bottom part; and an I-builder that alternately builds either a wire or a builder on the cell at the end of the wire. This makes it possible to build something on the next op along, then provide input to that op, then replace that op with something else, provide input to the replacement, etc.. This makes it possible to build anything using the following mutually recursive algorithm: to build on a given op, build a builder on the previous op, then build a wire up to that builder, then send a value along that wire to tell the builder to build.; and to build a wire up to a given op, build a wire on the op before, then build a wire up to the newly built wire. (This algorithm is exponentially slow – there ways to speed it up a little, but the linked program is nonetheless still pretty slow to build.)
The linked construction takes a constant (although fairly large) amount of time to build one new repeat of the pattern that makes up the stack. In order to do this, it needs to both build the stack pattern itself, and also to build a new universal constructor further to the right. The only part of the construction that is not straightforward is to cause a "changeover" in which one universal constructor stops alternating between its two states, and just becomes a wire permanently, whereas the newly built universal constructor starts to run (rather than being an inert object, like it is during building). In the linked construction, this is achieved using an I-builder, which makes it possible for the old constructor to build a wire up to the builder of the new constructor and send data through it (I-builders act like wires when they aren't building). The data sent through the I-builder is connected to another builder, which builds a wire from the old constructor to the new one and causes the new one to "power up", getting data inside its hexagon and causing it to start building (which overwrites the wire that went into the I-builder with the alternating pattern of "builder that builds to the right" and "wire that sends to the right" that allows the universal constructor to work). At the bottom of each universal constructor is a builder that runs unconditionally as long as the universal constructor is running, and which builds a break in the hexagon of the constructor to the left, causing it to stop; thus, once the new constructor has non-NIL values in its hexagon, it will break the constructor to the left and cause it to stop building, so that the wire at the point of its I-builder can permanently be a wire (which is necessary to be able to send data to the new constructor).
This is therefore sufficient to prove Trianguish to be Turing complete; you can use very long wires in the Esimpl-interpreter part of the program to ensure that it runs sufficiently slowly that the stacks will always have time to grow before they fill, in order to get an implementation of Esimpl that has unbounded stacks, and sufficiently many stacks and stanzas to be Turing-complete.
See also
- Game of Life, another cellular automaton, which is Turing-complete in a similar way to Trianguish