Wave.colors
Wave.icons
lifesim2.rle (zipped)
Wave is a cellular automaton I devised a while ago, but didn't bother finishing my Life emulator until now, because synchronising is ridiculously tedious. Anywho...
The Wave Cellular Automaton
This is a CA similar to von Neumann, but with 12 states and roughly four times the dimensions. It is, of course, capable of universal computation and construction.
The 11 non-ground states are divided into four groups: construction (1-3), signal (4-5), flag (6-7) and confluent (8-11).
Signals are sent through empty space (as opposed to a wire). Each signal is an orthogonally connected pair of states 4 and 5, which travels one cell per generation such that the state 4 cell is on the "left" of the signal and the state 5 cell is on the "right". Signals do not have to be separated by any blank cells - two adjacent signals can travel without any problems.
The confluent states are used to turn signals and to form logic gates and crossovers. A crossover is a 4x4 pattern which has the middle four cells and the four corner cells in state 8 (when at rest). Logic gates use the same pattern as crossovers, but may have each of the four corner cells in states 0, 6 or 7, to determine the orientation and behaviour of the gate. Each of the four sides of a gate behaves in the way specified by the corner cell clockwise of it (e.g. the west side is determined by the northwest corner cell). State 0 indicates that the side will be "satisfied" iff it is not receiving a signal; likewise, state 6 indicates it will be satisfied iff it is receiving a signal. State 7 indicates that the side is always satisfied, and will produce an output signal iff all four sides of the gate were satisfied exactly three generations ago. Crossovers and logic gates use the center four cells in combinations of the confluent states to work. Additionally, a single cell of state 10 can be used to turn or split a signal slightly faster than a logic gate would.
Construction works by using a "construction head", which moves through otherwise empty space (as opposed to a head on the end of a wire a la von Neumann). The construction head is a pair of state 6 cells. When such a head receives a suitably aligned signal, it will use a combination of states 0 through 7 to turn, construct or retract, depending on the following pattern of signals. There are eight possible actions for a construction head to take, listed below:
Code: Select all
x = 58, y = 7, rule = wave
2F6.2F6.2F6.2F6.2F6.2F6.2F6.2F3$DE6.DE6.DE6.DE6.DE6.DE6.DE6.DE$8.DE
14.DE14.DE14.DE$16.DE6.DE22.DE6.DE$32.DE6.DE6.DE6.DE!1001: become a 2x2 square (not intended for actual use)
1010: turn left
1011: turn right
1100: retract
1101: construct state 6 and retract
1110: construct state 7 and retract
1111: construct state 8 and retract
Universal destruction is not yet possible but I am considering implementing it in a later version.
The Life Emulator
I have constructed in Wave a pattern of dimensions 512x512 and period 2048, which behaves as a metacell for Life or any other Lifelike CA. The lifesim2.rle file contains a small grid of these metacells which is set up to simulate the evolution of a traffic light from a T-pentomino. Within each metacell, the presence of a east-facing signal at position (352,1) indicates that the simulated Life cell will be alive in the next generation. This causes a 384x256 rectangle (which could be made slightly larger) to "light up" and sends eight signals outward to the neighboring cells.
The rectangle (32,40)-(223,87) contains a three-bit counter, made up of 17 28x16 half adders, arranged in a 7x3 grid. The output is in three lines to the east, and one carry bit going northwards, which is caught and reflected to the right to make a four-bit output. This four-bit output is received by the ROM table to the right, which contains a twelve-cell column for each possible live cell count. The birth rules are stored in rows 12-19 of the metacell, and the survival rules in rows 20-27. The RLE file has each cell set up to behave under the rule B23/S3 but this can be easily adapted to other rules.
The rectangle (249,108)-(285,177) contains mechanisms to light up the metacell. In the top half is a device resembling a flip-flop, which sends output signals only when the input value (as considered every period of 2048 generations, of course) changes. The bottom half contains coders which output the sequence 111 (to turn on the "light") and 1100000000010001 (to turn it off). These codes aren't actually documented - any such device working to the original Wave specification would have to use a "software" method (i.e. a flip-flop) rather than the "hardware" method presented here (constructing and destructing).
Comments
- This is certainly not the first CA of this type I have engineered for the purpose of making an intuitive universal computer-constructor, and I'm sure it won't be the last as there is still plenty of room for improvement (see further comments). This is a much harder project than I first thought, and I can easily see myself starting from scratch many more times in order to create a more efficient CA.
- The lack of an OR gate is a nuisance, as any ORing must be done with a NOR-NOT combination. XOR gates also end up quite large as they have to be built up from the "(A AND NOT B) OR (B AND NOT A)" or "(A OR B) AND NOT (A AND B)" combinations.
- A lot of space is wasted on delaying signals. I may want to look in to making a CA that supports compact timers of some sort.
- One cell of von Neumann is just about equivalent to a 4x4 square in Wave, which makes things enormous. I have some ideas of how to reduce this to 2x2, while imposing a few extra restrictions (such as requiring signals to be an even number of cells apart, and still needing a larger-than-2x2-area for some logic gates).
- As mentioned, there's no universal destruction. I will want to make the construction head capable of destruction as well.
