ConwayLife.com - A community for Conway's Game of Life and related cellular automata
Home  •  LifeWiki  •  Forums  •  Download Golly

Small computers in WireWorld

For discussion of other cellular automata.

Small computers in WireWorld

Postby A. Erkiaga » October 20th, 2018, 5:16 pm

It could be interesting to try to find a very small pattern that is capable of arbitrary computation. Of course, in order to fulfill this requirement, such pattern would need to be infinite in size, so one can allow a simple memory device, like an arbitrary-sized loop of wire, not to be counted as part of the pattern, and instead focus on the "CPU" holding the actual logic. Any good examples?
A. Erkiaga
 
Posts: 14
Joined: November 1st, 2016, 12:24 pm

Re: Small computers in WireWorld

Postby A. Erkiaga » October 20th, 2018, 5:20 pm

Here is one:

x = 19, y = 17, rule = WireWorld
.17C$C17.C$C10.C2.B3.C$C8.4CA.C2.C$C7.C2.C2.C3.C$C7.C.3B5.C$C7.C2.C6.
C$C7.C.C.2C4.C$C6.2C.C3.C2.C$C4.2C2.C3.3BC$C3.C3.3C3.C$C2.C2.C2.C.BA.
C$C2.C.C.BA3.AC$C2.C2.A2.C.BA$B3.C3.3C$.A2C.2C2.C$7.2C!

It works by simulating Wolfram Rule 110, which is known to be Turing-complete. The given tape holds 15 cells. The control logic fits in a bounding box of 13 x 15 and contains 62 cells.
A. Erkiaga
 
Posts: 14
Joined: November 1st, 2016, 12:24 pm

Re: Small computers in WireWorld

Postby A. Erkiaga » October 20th, 2018, 5:47 pm

Smaller but slower 6-tick version:

x = 14, y = 20, rule = WireWorld
.12C$C12.C$C12.C$C12.C$C12.C$C12.C$C5.2C5.C$C3.2C2.C4.C$C2.C3.3C3.C$C
3.C3.C4.C$C3.C2.C.C3.C$C3.C2.C2.C2.C$C3.3C2.4C$C2.C2.C3.C$C2.C.4C.C$C
2.C.C2.2C$C2.C.4C$C2.C2.C$C3.2C$.CBA!

This has a bounding box of 9 x 13, and a population of 45 cells.
A. Erkiaga
 
Posts: 14
Joined: November 1st, 2016, 12:24 pm

Re: Small computers in WireWorld

Postby A. Erkiaga » October 20th, 2018, 6:37 pm

This one is better:

x = 13, y = 17, rule = WireWorld
.B2CAB2CAB2C$A11.A$C2.BA2CBA2CB$C.C$B2.CAB2CABC$A10.C$.2C7.A$3.C5.B$
3.B5.C$3.A5.C$.BC6.A$A2.C5.B$.C.4C2.C$C.2C3.C.C.B$B2.C2.4CA.C$A.3C2.C
.C.C$.C.C.2C!

Uses complex representation on tape. 7 x 13, 34 cells.
A. Erkiaga
 
Posts: 14
Joined: November 1st, 2016, 12:24 pm

Re: Small computers in WireWorld

Postby A. Erkiaga » October 20th, 2018, 7:07 pm

Maybe could simplify further by using a rule other than W110...
A. Erkiaga
 
Posts: 14
Joined: November 1st, 2016, 12:24 pm

Re: Small computers in WireWorld

Postby Redstoneboi » October 20th, 2018, 11:04 pm

A. Erkiaga wrote:Maybe could simplify further by using a rule other than W110...

the problem is that W110 is already relatively simple, and it’s the only rule we know of, other than reflections and inversions, that’s turing complete.
c(>^x^<c)~
This is Fluffy the cat.
Fluffy wants to discover new things that everyone likes.
Fluffy likes to watch spaceship guns in Golly.

There’s one problem,

Fluffy doesn’t exist :(
User avatar
Redstoneboi
 
Posts: 283
Joined: May 14th, 2018, 3:57 am

Re: Small computers in WireWorld

Postby A. Erkiaga » October 21st, 2018, 5:58 am

Yeah, you're right. I'm having a tough time trying to make a simpler Turing-complete system, even considering other things apart from CA! But here is a reduced version of the previous pattern:

x = 13, y = 18, rule = WireWorld
2.B2CAB2CABC$.A10.C$C2.A2CBA2CBA$C.B$B2.2CAB2CABC$A11.C$.C8.BA$2.C6.C
$2.C6.C$2.B6.A$2.A6.B$3.CB4.C$2.B.B2C2.C$.A2.B2.C.A.C$2.2C2.3CAB.C$.C
2.B2.C.A.A$B2.CB2C$.AC.B!

Same bounding box, but only 32 cells.
A. Erkiaga
 
Posts: 14
Joined: November 1st, 2016, 12:24 pm


Return to Other Cellular Automata

Who is online

Users browsing this forum: No registered users and 2 guests