Not The Main Worb
| Paradigm(s) | particle automaton |
|---|---|
| Designed by | User:Quintopia |
| Appeared in | 2014 |
| Computational class | Finite state automaton |
| Reference implementation | None |
| Influenced | noit o' mnain worb |
| File extension(s) | .ntm |
Not The Main Worb is a 2014 cellular automaton derived by User:Quintopia from Chris Pressey's Noit o' mnain worb (nomw) and inspired by User:ais523. It simultaneously enriches and simplifies the original automaton, making wire-crossings and amplifiers possible.
States
There are six possible states in a Not The Main Worb (NTMW) program:
- Bobule
- Hole
- Transmitter/Bobule
- Transmitter/Hole
- Receiver/Bobule
- Receiver/Hole
Every Transmitter cell or Receiver cell has a label. Any Transmitters and Receivers that have the same label are associated with one another. The number of labels available is implementation-dependent, but could be unbounded. As such, counting differently labeled states as different states, the NTMW automaton may have infinitely many possible states.
Transition Function
At every step in a NTMW program, cells in states Bobule or Receiver/Bobule swap their Bobule/Hole attribute with a randomly selected neighbor in their Moore neighborhood (including themselves). Intuitively, then, Bobules swap into a random adjacent cell (or not) in each step.
Any time a Transmitter/Hole cell becomes a Transmitter/Bobule cell, it will remain in that state until all other Transmitter cells with the same label also become Transmitter/Bobule. In other words, Bobules stick to Transmitters until all associated Transmitters have a Bobule on them. Likewise, any time a Receiver/Bobule becomes a Receiver/Hole, it remains in that state until all other Receivers with the same label become Receiver/Hole. When both of these conditions are satisfied for a given label, all Transmitter/Bobules with that label become Transmitter/Holes, and all Receiver/Holes with that label become Receiver/Bobules. Intuitively, when all associated Transmitters are filled with Bobules, and all associated Receivers are free, the Bobules are all consumed and the Receivers all produce Bobules.
It should be clear that these two types of state transition (which fully define the transition function of NTMW) are PT-symmetic: reversing time in the automaton is the same as switching Bobules with Holes.
Representation
It would be quite impractical and unintuitive to represent an NTMW initial state map using one character per cell due to the possibility, say, of a Transmitter having any of a large number of labels while also either having or not having a Bobule on it. However, using an image representation would be quite intuitive. Let each pixel be a cell. Let the red component be the label (where zero means "not a Transmitter or Receiver"), the MSB of the green component be the Transmitter (on) or Receiver (off) state attribute, and the MSB of the blue component be the Bobule (on) or Hole (off) attribute. Thus, our original six states will appear mostly:
- Bobule = blue
- Hole = black
- Transmitter/Bobule = cyan to white
- Transmitter/Hole = green to yellow
- Receiver/Bobule = blue to purple
- Receiver/Hole = black to red
In addition, although this language has no specified equivalent of nomw's Load Indicator, if an implementation should want to include such a feature for testing or output purposes (for instance, use it to increment a counter to see how many Bobules used a particular Transmitter), the second-to-most significant bit of the green component would make a fine selector bit for this purpose.
It is also possible to output an ASCII board. The reference interpreter displays all Bobules as danishes ("@") and Transmitter/Holes and Receiver/Holes as their representative symbols.
ASCII File Format
The file format consists of a starting board, followed by a line containing only a single octothorpe ("#"), followed by a series of lines containing Transmitter/Receiver symbol pairs.
In the board section, each line is a row of the board, and each pair of characters is a cell of that board. The first of each pair can be either a period (".") representing a bobule or a space (" ") representing a hole. The second of each pair is either any non-whitespace character, which serves as a representative symbol for a Transmitter or Receiver, or a space, which is not a Transmitter or Receiver.
In the Transmitter/Receiver map section, each line contains a single pair of characters. The first character is declared the symbol of a Transmitter and the second character is declared the symbol of its corresponding Receiver. No symbol may appear in this list more than once. Transmitters and receivers declared here do not have to appear on the board.
An example:
.#.#.#.#.#.#.#.#.#.#.#.#.# .#. . . A a .# .#. . . B b .# .#. . . C c .# .#.#.#.#.#.#.#.#.#.#.#.#.# .X # #X Aa Bb Cc
Walls
The equivalent of nomw's walls can be achieved by using Receiver/Holes (or Transmitter/Bobules) with one associated Transmitter/Hole which is entirely separated from all Bobules. Indeed, all walls in a given program can use the same label. To this end, an implementation of NTMW may treat all programs as if they were embedded in a infinite plane filled with Transmitter/Bobule all of which have the maximum possible label (or a special 'positive infinity' label in unbounded implementations).
Consider the use of the "#" Transmitter/Bobules in the above example and their corresponding "X" Receiver/Bobule.
Half-walls
The equivalent of nomw's half-walls/one-way cells can be achieved by placing a Transmitter directly adjacent to its associated Receiver. Every such pair requires a unique label to be used for this purpose.
Consider the Aa, Bb, and Cc Transmitter/Receiver pairs in the above example. These will eventually cause all nine bobules to be glued to the right side of the board.
Sources and Sinks
If a Transmitter (or set of associated Transmitters) has no associated Receivers, the condition on the Receivers for the transition function is trivially fulfilled, and it will immediately consume any Bobule that lands on it (or consume all Bobules which land on all of them when they are all filled). In other words, it behaves exactly like one of nomw's sinks. Likewise, Receivers with no associated Transmitter behave like nomw's sources.
An example using the ASCII file format:
.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# .#.S s.# .#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.# .X # #X @S sg
"S" is a source (because it is a Receiver with unused Transmitter "@") and "s" is a sink (because it is a Transmitter with unused Receiver "g")
Wire-crossing
The Transmitter/Receiver pairs need not be adjacent, though. One can put them on opposite sides of several walls. It should be obvious how to use this to create two perpendicular and crossing flows of Bobules.
Amplifiers
The number of Transmitters with a given label need not equal the number of Receivers with the corresponding label. If one associates one Transmitter with two Receivers, one can readily amplify the number of Bobules in a stream.
Logic Gates
One can construct logic gates in NTMW, using pairs of "wires" (lanes lined by walls), one of which contains Bobules (True) and its complement, which does not (False).
- OR: Combine two wires into a third wire with a half-wall at the end of each. AND their complements.
- AND: End two wires with Transmitters and begin a third wire with their associated Receiver. OR their complements.
- NOT: Swap a wire with its complement, using a Transmitter and a Receiver in each.
All other logic gates can be constructed from combinations of these three, which means any boolean circuit can be constructed using these plus various sources, sinks, and wire crossings. This implies that one can construct PSPACE-complete families of NTMW programs.