Page 1 of 1

Resources pertaining to computation in cellular automata

PostPosted: April 18th, 2018, 8:24 am
by blah
This is intended to be a list of circuit rules, computers, and other things pertaining to digital logic in cellular automata so that people can see the prior work. It is not a list of turing complete systems; this is more about practical computation. The years on some of these may be wrong, but I think they're useful information in general. I have provided the names of people if I have their real names; otherwise I'd just be copying their username from the thread and you could see that yourself. Thanks to ishanpm for 3 of the system descriptions.

I encourage others to suggest systems and computers I've missed, details I've left out in my descriptions, or mistakes I've made/suggestions etc.

The computation compilation: Compcomp.
Systems

Wireworld (1987) Brian Silverman
Incredibly simple 4-state CA based on electrons interacting in nontrivial ways. Implemented by many programs.

Circuitry Simulator (2009) Jack Eisenmann*
A simulator with instant wire and discrete signals, using the opening and closing of "gates" (not to be confused with "logic gates") to perform computations, implemented in Flash.

Wave (2010)
12-state CA where the basic unit of computation is a configurable AND/ANDNOT gate. Uses an interesting system where gates handle signals continuously, although this makes it somewhat difficult to work with. Implemented in Golly. (Description by ishanpm.)

WWEJ3 (2010)
An 18-state extension of WireWorld that allows for universal construction. Uses 8 types of electrons that allow a wire to act like a construction arm. Implemented in Golly. (Description by ishanpm.)

Logic Land (2012) Jack Eisenmann
(thread here) Somewhat complex but very intuitive 17-state CA based on continous signals going through wires, and simple logic gates. Currently impossible to create in Golly; the only two implementations are the one linked above and this.

Bliptile (2012)
(see 1, 2)Simple 4-state rule similar to Wireworld (though apparently created independently).

LLLL (2014-2015) Lode Vandevenne
Complicated 33-state CA based on continous signals and logic gates made out of different media through which a signal can pass. Allows a small crossover. Implemented in Golly. Very good documentation.

Rychládrát (2016) ME!*
A rule that I made which has simple instant wire and is relatively high-level. Can currently be simulated only by Reasoning Realm.

Logic Land 2 (2016) Jack Eisenmann*
Not really a cellular automaton; contains instant wire. Interesting to note is that a signal will travel through multiple gates in one tick, as such performing arbitrary computation instantly, given enough gates to go through. Incredibly high-level. Only one implementation.

'Digital Circuit Simulator Rule' (2017)
32-state CA based on continuous signals and logic gates, whose function is determined by a specific cell indicating the logical operation to be performed. Contains states that allow for a 1-cell crossover. (I'm not really sure what to call it; the name seems purely descriptive and the rule itself is "Digital". Also, the ripple carry adder in the download in that thread was made by me, but no credit is given. :(). Implemented in Golly.

Pulse2 (2017-2018)
A rule based on electrons flowing through wires and interacting with gates, which themselves act like wires transmitting continuous signals, it's kind of interesting. Implemented in Golly.

Wire2 (2018) ME!!
A rule based on electrons passing through 2-cell wide wires discovered by me messing around in this rulespace using Reasoning Realm. Somewhat novel.

No Time At All (2018)
A rule in which signals, each of which can be one of two colours, move along wires until they reach junctions at specific angles, at which point they wait for other signals to arrive. The main purpose of the rule is to eliminate timing problems from circuit design. Implemented in Golly.

Wireworld Modern (2019) Jeremy Tan
A 9-state extension of WireWorld focused on tight construction of logic gates. Has positive and negative electrons that perform various logical operations when they interact, depending on the angle. Implemented in Golly. (Description by ishanpm.)

*Infinite speed of light, thus arguably not a CA
Computers

The Wireworld Computer (Wireworld, 1990-1992) "...David Moore and Mark Owen, with the help of many others..."
Likely the first 'real' computer in a cellular automaton. 16-bit TTA with 64 words of memory (52 generic), which gives it 1/8kb of ram. There is a really deep analysis here, although the English isn't all that great so hopefully you speak French. A browser simulation which allows the user to enter data into the machine is described here, available here (the blog post implies you have to use hexadecimal, but it just uses parseInt() so decimal can be used). I have created a programming language and several programs for this computer, available here.

Dick (Logic Land, 2016) ME!!!
Inspired very heavily by the Wireworld Computer. Much like the Wireworld computer, it is a 16-bit TTA with 5 7-segment displays showing an unsigned 16-bit number. It has 510.75 bytes (~0.5kb) of RAM.

Důvěřivý (Rychládrát, 2016) ME!!!!
(see 1) An 8-bit computer inspired mostly by Jack Eisenmann's DUO Adept, so it's his fault that the machine code is kinda inefficient. I didn't really understand the idea of registers, so (much like the DUO Adept (and Dick (and the Wireworld Computer))) all variables must be stored in RAM. It has 256 bytes (0.25kb) of RAM, 8 bytes of VRAM, an 8 bit PC, and 1 bit storing a "flag", used for conditionals. It has 6 buttons you can use for input, has an assembler and emulator, and several programs written for it. The name simply means computer in Czech.

'Programmable Computer' (B3/S23, 2016)
An 8-bit computer created in the game of life. It has 32 21-bit items of ROM to store a program, and 8 8-bit registers to use as variables (one of these registers is the PC). Has a simple display, showing a byte in binary, and a script to allow it to be programmed.

'Multicore Processor' (Pulse2, 2018)
16-bit simple processor, inspired very heavily by Zachtronics, which is evident in the way that it seems to be used as multiple very simple processors joined together to form a more complex algorithm. Each CPU contains 64 words of ROM (1/8kb), to store its program, and four 16-bit registers. I'm not really sure what to call it; it doesn't really seem to have much of a name.

Honourable mentions
All of the turing complete machines in the game of life:
A Turing Machine (2000) Paul Rendell
The Minsky Register Machine (2002) Paul Chapman
Spartan Universal Computer-Constructor (2009) Adam P. Goucher
'Turing Machine Simulator' (2018)

Whatever you would call the Quest For Tetris project (2016-2017). I call it cheating, personally; for one, I don't think it's in the game of life. I think it's in its own CA, so I'm not really sure where it would fit into the overall list, but it's definitely worth mentioning. By the way, it seems to have been finished slightly before Dick (?), so I guess if you count it I wasn't the first to make a computer since the Wireworld one? Hmm.

Digital logic has been implemented in plenty of simpler rules, like (other than the game of life) "Star Wars"/"345/2/4" (in which two adders have been created: 1 2).

This thing.

The Powder Toy has had plenty of computers created in it. I personally like this.

I would very much appreciate any assistance in expanding or improving this list, including writing your own sections on things or correcting mistakes or whatever.

(edit 1: added the powder toy) (edit 2 (2018-04-21): the url tag for the MRM no longer takes up the whole line) (edit 3 (2018-04-29): Added Wire2.) (edit 4 (2018-06-30): Changed link for Pulse2 to lead to a thread.) (edit 5 (2018-10-06): Corrected statement about Dick's memory size (two words have one bit missing), wrote description of "Circuitry Simulator", miscellaneous copy-edits.) (edit 6 (2018-12-19): added link to Wireworld Computer simulator and changed description of its RAM.) (edit 7 (2019-01-17): added descriptions for Wave, WWEJ3, and WireWorld Modern contributed by ishanpm, added mention of BWCSL, fixed parenthesis on the Pulse2 computer.) (edit 8 (2019-01-20): WWC has 52 generic words, not 51.) (edit 9 (2019-01-21): added links to Rychládrát and Důvěřivý documentation.) (edit 10 (2019-01-25): added Freywa's name.) (edit 11 (2019-05-27): added NTAA.)

P.S. It would be nice if people actually bothered to give their creations proper names more often.

Re: Resources pertaining to computation in cellular automata

PostPosted: April 18th, 2018, 9:02 am
by danny
I hope this isn't off topic, but would non-totalistic two state rules with computers in them be included? I ask because I may build a computer in Snowflakes, and I think you would like it, but the only non-ruletable rule here is Star Wars so I am wary on whether it would qualify

Re: Resources pertaining to computation in cellular automata

PostPosted: April 18th, 2018, 9:08 am
by blah
danny wrote:I hope this isn't off topic, but would non-totalistic two state rules with computers in them be included? I ask because I may build a computer in Snowflakes, and I think you would like it, but the only non-ruletable rule here is Star Wars so I am wary on whether it would qualify

I included Coban's 8-bit computer in the game of life, so yeah, if you make a computer in a Hensel rule (which is totally what they should call those) it will probably be included in the main list of computers.

Re: Resources pertaining to computation in cellular automata

PostPosted: April 18th, 2018, 6:30 pm
by AforAmpere
Transers might be possible to build circuits in as well. Does anyone know of any logic gates in it as of now?

Re: Resources pertaining to computation in cellular automata

PostPosted: April 20th, 2018, 5:32 pm
by fluffykitty
The QFT computer can be compiled to GOL (hypothetically).

Re: Resources pertaining to computation in cellular automata

PostPosted: April 20th, 2018, 6:52 pm
by blah
fluffykitty wrote:The QFT computer can be compiled to GOL (hypothetically).

Yes, but if I make a B3/S23 Wireworld metacell does that mean that the Wireworld Computer is a computer in the game of life? I think that there's an unavoidable level of subjectivity in the finer details and distinctions here, and in my subjective opinion I think that the QFT computer was not created in B3/S23, but in its own wire automaton. I don't think that calling it a computer in the game of life really serves the purpose of the list; it does not describe the work that was done in practice.

Also, it's ugly.

Re: Resources pertaining to computation in cellular automata

PostPosted: January 17th, 2019, 2:03 am
by ishanpm
Yay, my CA is kind of interesting! My mission is accomplished :D

The QFT computer might not really be in CGOL, but there's just something that tickles me about writing a game of Tetris inside a language that compiles to a machine language that's run on a computer designed in a CA that's modeled in metacells inside another CA.

Also, here are some more systems to add to your list:

Wave (2010)
12-state CA where the basic unit of computation is a configurable AND/ANT gate. Uses an interesting system where gates handle signals continuously, although this makes it somewhat difficult to work with. Implemented in Golly.

WWEJ3 (2010)
An 18-state extension of WireWorld that allows for universal construction. Uses 8 types of electrons that allow a wire to act like a construction arm. Implemented in Golly.

Wireworld Modern (2019)
A 9-state extension of WireWorld focused on tight construction of logic gates. Has positive and negative electrons that perform various logical operations when they interact, depending on the angle. Implemented in Golly.

Re: Resources pertaining to computation in cellular automata

PostPosted: January 17th, 2019, 3:22 am
by blah
Someone finally added to the list!
I remember intending to list VarLife as its own CA and then listing the QFT computer as a computer in that CA, but I never got around to it. Maybe at some point I will.
ishanpm wrote:Also, here are some more systems to add to your list:

Thanks. I'm going to add these, but the Wave description seems to have a typo or some obscure terminology I don't understand. What is an ANT gate? Did you mean ANDNOT gate?

Re: Resources pertaining to computation in cellular automata

PostPosted: January 17th, 2019, 12:23 pm
by ishanpm
blah wrote:What is an ANT gate? Did you mean ANDNOT gate?


Yeah, I mean ANDNOT. I've seen it referred to as ANT in a few places, but I can't find any examples.

The way Wave handles logic is pretty interesting. Every gate is a 4 by 4 block of cells, with some flags on the corners that indicate whether each side is a positive input, negative input, or output. The same shape is also used for crossovers. So an XOR might look like this:

x = 45, y = 15, rule = Wave
4.F18.F$.2H2.2H13.2H2.2H2.2H2.2H10.G$.2H2.2H13.2H2.2H2.2H2.2H10.G$F2.
2G14.F2.G3.G3.G3.G$3.2G7.F6.F2.GH2.H3.G$.2H2.2H13.2H2.2H2.2H$.2H2.2H
13.2H2.2H2.2H$3.F3.G4.F9.GH2.HF$16.F6.F2.GF2.G$6.J2.2H13.2H2.2H$9.2H
13.2H2.2H$8.G2.G4.F9.G$8.G2.F$5.J3.2H$9.2H!

Re: Resources pertaining to computation in cellular automata

PostPosted: March 4th, 2019, 3:25 am
by PHPBB12345