ConwayLife.com

Posted: **March 15th, 2019, 5:15 am**

You can implement any n-state Margolus neighbourhood rule with just n^4 tiles: each one is a truncated octahedron (with 6 square faces and 8 hexagonal faces) where the hexagonal faces are decorated with indentations/protrusions and the square faces are completely flat.

This is based on the BCC tiling of truncated octahedra:

https://en.wikipedia.org/wiki/Bitruncat ... _honeycomb

By exploiting symmetry, Fredkin and Toffoli's BBM automaton requires only 6 tiles (!!!) instead of 16.

Posted: **March 15th, 2019, 10:15 am**

calcyman wrote: By exploiting symmetry, Fredkin and Toffoli's BBM automaton requires only 6 tiles (!!!) instead of 16.

That's also true using lego-like squares as I claimed above for Critters. The two cases are probably equivalent. Anyway, I think we can agree that Margolus neighborhoods are a lot easier to handle than Moore neighborhoods. A ball and stick model with BCC adjacencies would make the interior more visible.

ADDED: I think I can put together Margolus tiles with appropriate bumps and dents using a 4x4 lego plate and some smaller plates and tiles to fill in the gaps to make shapes that will fit together without connecting. It's possible I have to go beyond 4x4. I haven't worked out the details. Legos are a kind of expensive solution, but posting a plan is free except for the time spent.

ADDED later. Anyone see a problem with this plan? (YES: I just realized there is nothing preventing you from putting a 0 output into a 1 input and leaving an internal gap; I would like to fix this without moving up to bigger plates, but I'm not sure it's possible) The terms brick, plate, and tile are consistent with this catalog I think, and standard. The lego tiles just create a non-connecting surface so you don't have to pull it apart to reuse. I guess they could be omitted in a permanent construction.

a 1x2 brick (thickness 3)
b 2x4 brick (thickness 3)
c 4x4 plate (thickness 1)
d 1x4 tile (thickness 1)
e 1x2 tile (thickness 1)
f 1x1 plate (thickness 1)
g 1x1 tile (thickness 1)

Blank tile:
Assemble in bottom to top layers.

Code: Select all

 .aa.
bbbb
bbbb
.aa.

cccc
cccc
cccc
cccc

dddd
e..e
e..e
dddd

0-bit input:
Stack of 2 1x1 plates (f) attached to bottom corner of 4x4 plate (c)

1-bit input:
A single 1x1 plate (f) attached to bottom corner of 4x4 plate (c)

0-bit output:
Stack of a 1x1 plate (f) and 1x1 tile (g) attached to top center square of 4x4 plate

1-bit output:
Stack of 2 1x1 plates (f) and 1x1 tile (g) attached to top center square of 4x4 plate

Blank tile is thickness 5 except for input/output.
0-out, 0-in are both thickness 2, so thickness is 5 including 4x4 plate
1-out is thickness 3, 0-in is thickness 1, so total thickness is 5 including 4x4 plate.

Note: these are all pretty common lego pieces and if you're not picky about colors, you might get them in the assortments sometimes offered by empty-nest parents.

I had a chance to test some of this with a few legos lying around but not the complete construction.

ADDED: Finally, to bring this back to CGOL, I am sure that the polyomino implementation could also be made with legos, the only question being how many. This is impractical, but a proof of concept construction might be good publicity, since legos are popular, and doing something that sounds like science with toys usually gets attention. Another possibility is nanoblocks. They don't have as big a built-in audience, but the size is more practical.

And a compiler from general CA logic circuits to standardized lego build instructions would be popular, I think, even if the plans are rather impractical in time and money.

Posted: **March 16th, 2019, 12:33 pm**

Starting a new post with a much better design for Margolus neighborhood legos. I was able to scrounge enough Legos around the house to prototype one, but I don't have a 4x4 plate, so I had to use a 4x6 and ignore the extra part. [Note: I am a lot more interested in CGOL, but this is low-hanging fruit to work on this weekend.]

The construction requires 17 pieces for each neighborhood window.
a) 1 4x4 plate,
b) 8 1x2 plates,
c) 8 1x2 tiles.

The base piece is just the 4x4 plate. It's best to describe input/output units relative to a corner of the 4x4 plate, since they change with rotations:

Upper left is always a corner of the 4x4 plate, whether viewed from top or bottom, "." means no piece on this layer, layers are given bottom to top.

Output of 0 (attach to top)

Code: Select all

cc
bb

..
cc

Output of 1 (attach to top)

Code: Select all

cb
cb

.c
.c

Input of 0 (attach to bottom)

Code: Select all

.b
.b

Input of 1 (attach to bottom)

Code: Select all

..
bb

The result has a tiled top that will fit with other pieces but not connect. The 4 center squares always have thickness 4, while the corners always have thickness 2. The other 8 squares can have thickness either 2 or 4 and have to match tiles above and below. They will never fit with a hidden gap (the flaw in the first design).

It alternates neighborhoods because the corners form an offset square pit that matches the thicker center of the piece placed above. Likewise, the center has a bump that matches the thinner corners.

Here is a piece I constructed that is intended to implement this Critters rule and all four rotations (corrections welcome as always):

Code: Select all

00 --> 11
10     01

The bottom orientation comes from flipping on the horizontal axis. Please ignore the left two columns of the 4x6 plate.

: Screen Shot 2019-03-16 at 11.10.56 AM.png (81.91 KiB) Viewed 72047 times

I'm going to see if I can produce something nicer looking in lego design software.

ADDED: I can simulate the previous neighborhood (corners of nearby windows) to verify the fit.

: Screen Shot 2019-03-16 at 11.11.05 AM.png (79.06 KiB) Viewed 72047 times

You can't see it in the photo, but it fits very well!

Practical note: based on bricklink, all three of the lego parts are inexpensive. You need a lot to do anything interesting though. The other issue is, because the layers alternate, you get overhanging pieces. I'm not sure it will be stable. If not, you can make half-pieces or even longer strips with zero values (or alternating in a CA like critters). This definitely seems like a feasible project with legos.

ADDED: I wonder if the polyomino tiles for CGOL can be converted into these kind of grooved pieces with a rectangular profile but varying thickness. I will have to read the details more carefully to convince myself one way or the other.

Posted: **March 16th, 2019, 1:24 pm**

@calcyman I think it's simpler to implement marolious N^4 cases just by placing square on top of a square, only forcing the margolius switch of the squares in the next layer (think of a rod sticking out of the center of the square). As two margolius switches are the same we don't need two copies of such tiles. I think it would be interesting to make more states BBM automaton (connecting the beginning and the end), to include different angles. Thus maybe simulating gases with tiles, but gasses are not computationally complete, yet still chaotic.

@pacallahn Another interesting point is computational universality proof. So I found an article. What rules do you know to be computationally and preferably construction universal? There are usually conservation laws in reversible automatons, and you can't lose information. When you ask an automaton to calculate 2 + 2 you don't want the automaton to return you 2 + 2 = 4, you only need the 4. It's inevitable to lose computational efficiency by using reversibles. No one is using anything here for any specific purpose just want to point out that maybe it's interesting to find such set of tiles that does something simpler. Like adding, substractind, multiplying, dividing two numbers. I mean is there a lego set of this sort? Pieces that you make any computation of any kind using just lego bricks? Maybe we can start from simple adder, if there is none? You stuck your lego bricks of 0 and 1 in the line, then you have 8 special brick that input the A,B,C channels from previous addition and output the next C and result bit. Those are just 8 tiles, still making something clearly comprehendable and showcasing the computational power of tile puzzles like this. I mean this could be a kids toy, where they learn to count using solving addition puzzles. They will add 1 all the time until they get the point of counting. This is still more than 6 tiles billiard calcyman talked about but they can come in parallel. The only difference is that adders are 8 pieces and linear, and billiards are 2D and can be played by smaller ages probably as they show only movements and not numbers, which is more intuitive. It will be interesting to see kids that learn the binary system first and then readjust to decimal system. I know someone who is raising his child this way, or at least trying and I'm sure this kind of ideas have some market. This is just a bit more complex than regular lego.

Posted: **March 16th, 2019, 1:52 pm**

simsim314 wrote:There are usually conservation laws in reversible automatons, and you can't lose information.

You can't lose it, but you can send it far away. Whether or not real physics is reversible, you can embed computers in reversible physics, whether classical dynamics or something like billiard ball models. For "practical" purposes of CGOL constructions, this is mostly an inconvenience, but I think there is a lot of flawed intuition about reversibility (as I noted in another thread). True, you cannot collide gliders and make a stationary oscillator in a reversible CA, but you can make a stationary oscillator while sending off one or more gliders into the distance. Over time they go off into infinity, holding as much old information as you want. Run it in reverse and you eventually get it back. But ignore the receding glider and you have essentially a synthesis in the CGOL sense.

And real computation is analogous. It's roughly why you need to a fan to take the heat away from your computer. Whether you lose information in the real world or not, we already have the basic framework for throwing it away. In CGOL, there is this wonderful property that you can make it disappear by producing empty space, but you don't need that.

I am certainly not saying reversible computation is better or that it should be the main focus. Once you understand that you don't have to throw away information, it is simpler to use an abstraction that does throw it away. But Margolus neighborhoods work really well as lego constructions, so I want to see where I can take it this weekend. (My post above has some corrections and new pictures)

simsim314 wrote:Pieces that you make any computation of any kind using just lego bricks? Maybe we can start from simple adder, if there is none?

It sounds feasible. I can easily construct legos (custom or brick designs) that make a flat mural representing the rule 110 CA. This is universal but not obviously so. A Sierpinski triangle pattern is even easier but not universal. Something most people would understand (multiplying two numbers) would make an interesting project. Not sure how hard it is.

Posted: **March 16th, 2019, 3:05 pm**

Is there a good theory of computational transfer from one computation to another? For example could people playing some complex version of pac man actually search for P19 oscillator? I also don't want to force some sort of algorithm, in this way I can simply use lifesrc for example, I want human intuition to guide lifesrc in something which is computationally equivalent to running from creatures inside pac man/super mario, such that in the grand scale - the decisions done in the super mario game will be a complex search algorithm?

Posted: **March 16th, 2019, 6:41 pm**

simsim314 wrote:Is there a good theory of computational transfer from one computation to another? For example could people playing some complex version of pac man actually search for P19 oscillator? I also don't want to force some sort of algorithm, in this way I can simply use lifesrc for example, I want human intuition to guide lifesrc in something which is computationally equivalent to running from creatures inside pac man/super mario, such that in the grand scale - the decisions done in the super mario game will be a complex search algorithm?

That sounds ambitious, though I guess if you can reduce one NP-complete problem to another (e.g. 3-SAT to Hamiltonian Path) then you could probably get someone to solve a problem of arbitrary difficulty when they think they're just playing an extended session of Super Mario Bros. The reduction will usually add a lot of extra work and conceal whatever intuition might have existed in the original problem. I am not sure there is a good theory of how to come up with the reductions. I can think of how a video game might be like solving Hamiltonian Path (traps in rooms to prevent them from being reused, and you have to collect all the coins) but I don't know of any algorithm for taking two systems and finding the reduction, aside from composing a chain of known reductions transitively.

On another note, I almost think we've been using Margolus neighborhood and reversible CA interchangeably, though maybe you did not intend that. You can make Margolus CAs that are not reversible that would not have the problems Critters has with glider guns and synthesis. The main reason people don't is just that this neighborhood is ideal for defining a reversible CA, so that's what it's normally used for. But I see now that it's also very good for constructing tile-based implementations, so it might be worth considering other CAs like it. You might need to go beyond 2 states, though, to get something with as much flexibility as CGOL.

ADDED Here are lego instructions (PDF document) for building the Margolus tile described in my earlier post. I am using the "Studio" software available at bricklink. It's free though I don't know the publisher. I think we could make lego instructions like this for CGOL gadgets, though they may not be reasonable things to build.

There is one slight problem with the tiles based on 4x4 plate. They can fit together incorrectly if placed upside down. I'm not really interested in adding more legos to fix this. It may be enough just to say that the legos need to be placed right side up (the same way they need to be placed to fit tightly). This requires slightly more human judgement but seems like a reasonable compromise.

Posted: **March 17th, 2019, 7:00 am**

Actually it would be nice to find interesting Margolus rules with 3-4 tiles. I've found a subspace of 1024 rules using 4 tiles using the don't know tile - I'm sure this is implementable with basic lego as well.

1 1 --> x y
0 0 --> z t

1 0 --> u v
0 0 --> w k

1 x --> 0/1
x 1

0 0 --> 0/1
0 0

Now if a rule like CGOL would be found inside this rule space it would be the most simplistic universal implementation using tiles. The point of Margolus != reversible was crucial indeed.

As for the lego pieces - I'm amazed we can make it with regular lego and simplistic restriction like - place them next to each other and not on top. I would still prefer to enforce this part, as it feels to me the general point of lego to enforce some degrees and release some others, and the enforcement is valuable in my opinion. But to see the physical result we can start from lego indeed.

Posted: **March 17th, 2019, 1:15 pm**

simsim314 wrote: As for the lego pieces - I'm amazed we can make it with regular lego and simplistic restriction like - place them next to each other and not on top. I would still prefer to enforce this part, as it feels to me the general point of lego to enforce some degrees and release some others, and the enforcement is valuable in my opinion. But to see the physical result we can start from lego indeed.

I'm not sure I follow all your concerns. After letting it bother me a little more that the lego transitions can be used upside down, I realized that was just an unfortunate coincidence of the representation of zeros and ones. Here's a screen shot of an alternative model I put together in Studio. It uses three raised squares for 1 but keeps the same representation for 0 and preserves the property that the center is 4 layers thick and the corners are 2 layers thick.

: Screen Shot 2019-03-17 at 10.02.26 AM.png (56.63 KiB) Viewed 71988 times

The number of pieces does not change, because there are "2x2 corner" shapes for both plates and tiles. I think the cost is probably higher for the corner pieces and they might be harder to find in a bulk purchase (e.g. garage sale). Link to build instructions.

ADDED Even a 00/00 to 00/00 transition would not work upside down (I think) because the top and bottom would be mirror images. It is possible that we could use the ambiguous encoding (where 0-in looks like 1-out and vice versa) to permit smaller tile sets with some additional symmetries and allow the transitions to be placed upside down. That makes for ugly lego constructions, but it might be worth exploring. (Also don't want to get sidetracked from CGOL)

Posted: **March 17th, 2019, 2:55 pm**

If you are really serious about physical tiles, and since you want a small variety of small pieces, the one solution for bulk parts is a LEGO store.

Years ago some of my coworkers put together a QR code in bricks to promote our mobile phone apps. At the store, LEGO has a "Pick-a-Brick" wall, and restock them with standard sized boxes full of bricks. They bought what they needed that way. Because these boxes are for internal store use, the number of items in the box is what fits, not by exact count or weight, and generally not sold to the public.

They are also fixed price, and the last I heard, cost $100 (US). About 700 2x4 bricks fit into one, but about 2800 1x2 bricks fit into the same space. So you are looking at about 4600 brick lugs per box. For the plates and tiles, figure about 3 times that number, since they are 1/3 the height of bricks.

So find the manager of a store, explain what you are doing, and since you aren't going to be reselling them, they'll probably help you. This is the sort of project that appeals to the adults who run those places.

You can also find out if there's a local LEGO User's Group. Those folks usually have the ability to order direct from LEGO in bulk for their projects, so aren't limited to whatever they've got in the back of the store (again, not for resale.)

Or course, for our project, we didn't use the full box contents, so we had plenty of left-overs to use as programmer toys...

Posted: **March 17th, 2019, 4:24 pm**

hkoenig wrote:If you are really serious about physical tiles, and since you want a small variety of small pieces, the one solution for bulk parts is a LEGO store.

Fairly serious. Thanks for the advice. I like the idea of projects that illustrate computation without either human thought or electronic computers (or something that looks too much like a machine). Something that is not that much work and leverages a popular product like legos seems like it could gain wider interest. Either way, it was enough fun fitting prototypes together that I would like to go bigger.

ADDED: It's worth noting that in the case of Critters (at least), the simplified transitions work because they are symmetric and can be turned upside down without changing the transition. That means that keeping the pieces oriented up is an aesthetic recommendation, not a computational requirement. I now like this more than I did. I would like it even better if a piece could serve double-duty and implement two rules.

Let this be the transition window:

Code: Select all

a b  ->  e f
d c      h g

(Note that variables are in clockwise order, not row by row) When you flip a tile, the 1x2 representation of a bit is inverted, so we have this basis of operations for orienting a lego transition.

original: (a b c d) -> (e f g h)
flip: (~h ~g ~f ~e) -> (~d ~c ~b ~a)
rotate: (b c d a) -> (f g h e)

"The transition function for Critters counts the number of live cells in a block, and if this number is exactly two it leaves the block unchanged. If the number of live cells is zero, one, or four, the transition function flips the state of every cell in the block. And finally, if the number of live cells is exactly three, the transition flips every state and then rotates the whole block by 180°"

Thus, for all blocks anything other than two or three live cells:
original: (a b c d) -> (~a ~b ~c ~d)
flipped: (d c b a) -> (~d ~c ~b ~a)
rotated: (c b a d) -> (~c ~b ~a ~d)
Are the same as long as a=c, which works for (0 0 0 0) (0 0 0 1) (1 1 1 0) (1 1 1 1)

For three live cells:
original: (1 1 1 0) -> (0 1 0 0)
flipped: (1 1 0 1) -> (1 0 0 0)
rotated (3x or inverse): (1 1 1 0) -> (0 1 0 0)

For two live cells, this works:
original: (0 0 1 1) -> (0 0 1 1)
flipped: (0 0 1 1) -> (0 0 1 1)

original: (0 1 0 1) -> (0 1 0 1)
flipped: (0 1 0 1) -> (0 1 0 1)
Are also the same.

I believe that BBM fails, however.
One of the transitions is:

Code: Select all

0 0  --> 0 1
1 0      0 0

Flipping it we get

Code: Select all

1 1  --> 0 1
1 0      1 1

And that is not a valid BBM transition.

ADDED One more observation. As I was staring at a real lego example, I realized that every one of these has two uniform 4x4 layers that can be removed from the construction. The result is harder to design in legos and seems more fragile, but it is more like a burr puzzle and would be strong enough if connected at the 2x2 center. Here's what it looks like (same transition as before).

: Screen Shot 2019-03-17 at 11.55.22 PM.png (68.43 KiB) Viewed 71953 times

Building instructions are here.

In fact, there are only 4 shapes up to mirror images that can be the input or output of a transition:

: Screen Shot 2019-03-17 at 11.52.56 PM.png (10.47 KiB) Viewed 71953 times

If there was a way to produce them and snap them together, it might be a simpler way to make Margolus CA pieces.

Posted: **March 18th, 2019, 8:26 am**

pcallahan wrote: might be a simpler way to make Margolus CA pieces.

I actually like that this is basically lego. It's elegant.

pcallahan wrote:I'm not sure I follow all your concerns.

You can continue playing lego just placing pieces one on top the other without following the rules completely. I would like the pieces not to be attachable at all sometimes. This is my problem with lego. I'm thinking about 0/1/X lego. i.e. Lego where not everything is attachable to anything, but small pieces of lego that can design any "tile" set. We would also need "attach forever" mechanism and attach/detach. This would be minimal turing complete universal tile set, which will allow any computation by restricting the set. This could be competitor to Lego. I mean all tiles would be designable. You will get the set to make tiles, then you use the tiles to evolve CA. We need just to print the basic tiles. It's what you're trying to do with lego, and maybe this would be enough, but I would like to see a universal set that can define any tile set, and then use it like lego.

On other note. Don't you need to use 5x5 to stuck a cube in the center to enforce Margolus?

EDIT I've found the lego "cube" pieces of 72 different cubes, such that any tile set can be constructed and this tile set can enforce any rule (including CGOL for example).

The cube has up-bottom faces and 4 side faces. Each face can have several options.

Notations: 0 = "/", 1 = "\", X = "X", A = attach forever, S = plane square.

bottom: 0/1/X/A
top: 0/1/A
Side: A/S

Count: We will make it rotationally symmetrical, so side A/S have 6 options due to symmetry. Now the top has 3 and the bottom has 4. In total 72 basic cubes. If we can make the input and the output look the same i.e. top = bottom, then 54 basic cubes. If you're willing to get rid of X then 36.

EDIT I wonder if this is possible to make the still life tiles using the 36 cubes?

Posted: **March 18th, 2019, 9:59 am**

simsim314 wrote:On other note. Don't you need to use 5x5 to stuck a cube in the center to enforce Margolus?

Not unless I misunderstand your question or I've made a mistake. The basic 4x4 tile (lego or anything else looks like this):

Code: Select all

a??a
?bb?
?bb?
a??a

a and b are different thicknesses of layers each centered on the same plane. In my implementation, b>a so it is thicker in the center, but it could work the other way. Either way, corners of the next layer need to line up with centers of the previous layer so a/2 thickness matches b/2 thickness. The 2d equivalent (or a diagonal cross-section) looks like this, with a=2, b=4:

Code: Select all

.**.
****
****
.**.

With "colors" 0, 1, 2, 3 this is the diagonal cross-section.

Code: Select all

.00..11..00..11.
0000111100001111
.00221133002211.
..222233332222..
.00221133002211.
0000111100001111
.00..11..00..11.

That leaves 8 squares off the diagonals of the 4x4 square that can be used for encoding complementary values.

Posted: **March 18th, 2019, 11:10 am**

pcallahan wrote:The basic 4x4 tile

I didn't comprehend the second part. I'm not sure this will help still. Say the input is
a b
c d

The output shell be

x-y
---
z-t

I'm not sure if this is better - just a valid alternative.

----------------

On the side note I've managed to reduce the 72 tiles into 9 lower level tiles. The flow is now looking as follows:
Use 9 tiles to construct any of the 72
Use the 72 to construct a tile set.
Use the tile set to construct CGOL or whatever.

The universal 9 tile set:

I use 3x3x3 cube. The core is 1x1x1 and everything is attached to it forever. The other pieces:

Side piece is 2x1x1. They attached to the core (in circle) and have two cases - side_attach/plane square.

Now we have also top and bottom 3x3x1 attached. For the top we have three cases 0/1/bottom_attach, and for the bottom 0/1/X/top_attach. Mathematically it's possible to make bottom = top, so this is 4 but for aesthetics purposes I use 7. That's all - we get all the options this way.

In total for 3D printing: 7 (top + bottom) + 2 (side) + 1 (core) = 10. Attach now the top to the core to get 9.
Total mathematical: 4 + 2 = 6 (divide the core 50/50 between top and bottom as well).

It's amazing that 6 cuboids is enough for this purpose. I wonder could it define hexagonal/triangular rules as well, or do we need to start from scratch?

Anyway I think this is really time for jscad. Having 9 pieces is even less than 16 of the original 2d tiles. It's much more attachment work, but isn't this is the purpose of this exercise? To enjoy combining things together by hands, still feeling you're computing something?

BTW I guess this set of tiles is not known - as we even didn't know the CGOL tiles and this is two abstraction levels higher. Maybe it's possible to publish an article on this topic?

Posted: **March 19th, 2019, 2:16 pm**

simsim314 wrote:Anyway I think this is really time for jscad.

I'm looking forward to seeing it. I have gone a little quieter on the Margolus constructions while I work out the details and would like to see the CGOL tiles implemented in solid form.

I need to work a little harder to prove the that simplest Critter tiles don't admit invalid packings. In fact, I think a few pathological cases may allow sliding the tiles without changing the meaning. I am not sure if some are just completely incorrect. My goal (moving away from legos) is to fit each window into a 4x4x2 voxel box and preserve symmetry for the Critters case. This works as I already described except for ruling out invalid packings. (UPDATE: I think the "burr puzzle" version of the Critters components will admit invalid packings. If you have a 4x4 tile in the center, as in the original lego construction, this limits the possibilities, though it may allow sliding in some cases.)

Posted: **March 20th, 2019, 4:47 am**

pcallahan wrote: would like to see the CGOL tiles implemented in solid form.

I'm not sure the jscad project was clear. I'm not building CGOL tiles nor binary adder or any margolus rule. I'm building a lego set equivalent which will allow to implement any set of tiles which enforces any moore neighborhood CA. It's prototyping tiles for tile sets. This is tiles lego - a set of 9-10 pieces, which can be brought together to build sets of tiles in enforcing format. Obviously including 26 CGOL tiles but this is a lot of work - so probably I'll stick at first to simpler stuff like you're doing. Binary adder sounds like a good start to me.

It's like axioms for tile sets. To explain it a bit further I've 4 levels of abstraction:

9-10 - printed tiles. (axioms)
72 - combinations of the printed tiles to make attachable cubes. (basic theorems)
inf - combination of 72 cubes to generate any tile set. Margolus, CGOL, adder etc. (advanced theorems)
end user - takes the tile set and connects them together. (useful application)

Hopefully this tile set in itself will be educational. Obviously I'm not going to stick all the tiles from the axioms, but the fact that this is possible is very educational. The 3d printed tiles from CGOL could be fluently integrated with the same tiles built from axioms. Think of lego that you can always build from 10 smaller pieces, so if some part has lost you can always build it from the axioms instead of buying a new set.

Posted: **March 21st, 2019, 2:13 pm**

simsim314 wrote:I'm not sure the jscad project was clear. I'm not building CGOL tiles nor binary adder or any margolus rule. I'm building a lego set equivalent which will allow to implement any set of tiles which enforces any moore neighborhood CA.

Thanks for the clarification. I think this will still be very helpful in trying to follow the constructions.

Random comment (before I forget). I mentioned something like this before, but given the amount of empty space in a typical tiling, I wonder if we should have special purpose 0 to 0 blocks that would cover for powers of 2, like a 2^i x 2^j empty square over 2^k generations. It would be relatively easy to define them as an a union of functioning tiles, and for the purpose of building with them, it would save a lot of really tedious and pointless effort of calculating 0-0 transitions. Of course, it does make the model less uniform.

This would also open up the possibility of replacing the interior with a rod that would simply space the initial and final generation appropriately. It might make the active part of the pattern more visible.

Posted: **March 21st, 2019, 10:06 pm**

I've finished the 10 axioms tile set. It's 3d printing friendly - width of material included and most of the slopes <= 45.

Here is the openjscad code:

Code: Select all

//This is universal CA tile set axioms. 
//Invention and design by Michael Simkin 2019. 
//Constants
epsilon_material = 0.03;
depth_factor = 0.6;
symbolR_factor = 0.7; 
sumbolH_factor = 0.4;
symbolW_factor = 0.25;

attach_w = 0.34;
attach_h = 2.2;
attach_dp = 1.7;
attach_c = 0.2; 
attach_f = 2; 
attach_m = 1.1;
c_factor = 0.7; //the slope of attachment mechanism. 1 = 45, 0 = 0. 
v = 3; // The size of additional material
R = 10; //The length of internal core
d1 = 2.4;
d2 = 3;

h_extrusion = v * depth_factor;
sH = v * sumbolH_factor;
sR = (R + 2 * v) * symbolR_factor * 0.5;
sW = (1 - symbolW_factor) * sR; 
sWcube = symbolW_factor * sR; 
sideH = v - 2 * epsilon_material; 
topH = v - epsilon_material;

function make3D_printable(part, ep)
{
    return intersection(part, cylinder({r1:R*3, r2: 0,h:-R*3}).translate([0,0,R*3 + ep]));
}

function MainAttachMale()
{
    w = attach_w;
    h = attach_h;
    c = attach_c; 
    f = attach_f; 
    ep = epsilon_material; 
    dp = attach_dp-ep;
    tr = dp - f*c; 
      //return linear_extrude({ height: 10,  );  
    var p = polygon({points:[ [0,-c*c_factor+ ep],[0,f*c-ep],[-c+ep,ep]]});
    var main_part = make3D_printable(cube([w-2*ep, dp-ep, h]), ep);
    var exp = make3D_printable(linear_extrude({ height: h - tr }, p), epsilon_material).translate([0,tr,tr])
    
    return union(exp, main_part).translate([ep,0,0]);
}

function MainAttachFemale()
{
    w = attach_w;
    h = attach_h;
    c = attach_c; 
    f = attach_f; 
    ep = 0; 
    dp = attach_dp-ep;
    tr = dp - f*c; 
      //return linear_extrude({ height: 10,  );  
    var p = polygon({points:[ [0,-c*c_factor+ep],[0,f*c-ep],[-c+ep,ep]]});
    var main_part = cube([w, dp, h]);
    var exp = make3D_printable(linear_extrude({ height: h - tr }, p), 0).translate([0,tr,tr])
    
    return union(exp, main_part).translate([ep,0,0]);
}

function AttachEmale()
{
   m  = attach_m;
   return union(MainAttachMale(), MainAttachMale().mirroredX().translate([m, 0, 0])); 
}

function AttachEfemale()
{
    m  = attach_m;
    h = attach_h;
    dp = attach_dp;
    w = attach_w;
    
    return difference(union(cube([m, dp, h]), MainAttachFemale(), MainAttachFemale().mirroredX().translate([m, 0, 0])),cube([m, dp, 2*h]).rotateX(-45)); 
}


function AttachS()
{
    var mr = union(AttachEmale().translate([0,0,-attach_h]),AttachEmale().translate([0,0,-attach_h]).mirroredZ());
    return mr.rotateX(90).translate([-attach_m/2,0,0]);
}

function AttachF()
{
    var mr = union(AttachEfemale().translate([0,0,-attach_h]),AttachEfemale().translate([0,0,-attach_h]).mirroredZ());
    return mr.rotateX(90).translate([-attach_m/2,0,0]);
}


function Attach(ep)
{
    
    if(ep === 0)
    {
         return union(AttachS().translate([d2, 0, 0]), 
        AttachS().translate([0, d1, 0]), 
        AttachS().translate([-d2, 0, 0]),
        AttachS().translate([0, -d1, 0]));
    }
    else
    {
        return union(AttachF().translate([d2, 0, 0]), 
        AttachF().translate([0, d1, 0]), 
        AttachF().translate([-d2, 0, 0]),
        AttachF().translate([0, -d1, 0]));
    }
    
}

function Draw0(ep)
{
   l = (sR - sW)/2 + ep; 
   u = (sR + sW)/2; 
   
   return union(rotate_extrude( polygon({points:[ [u-l,0],[u+l,0],[u,l]]}) ).translate([0,0,sH+ep]),
    difference(cylinder({r:(sR + ep), h:(sH + ep)}), cylinder({r:(sW - ep), h:(sH + ep)})));
    
}

function DrawLine(ep)
{
   sw2 = sWcube / 2;

   var p = polygon({points:[ [-sw2-ep,0],[sw2+ep,0],[0,sw2+ep]]});
   var exp = linear_extrude({ height: 2*sR }, p).translate([0,sH+ep,-sR-ep]);
   
   return union(cube([2*sR+2*ep, sWcube + 2 * ep, sH+ep]).translate([-sR-ep, -(sWcube)/2-ep, 0]),
                 exp.rotateX(90).rotateZ(90));
}

function DrawPlus(ep)
{
    return union(DrawLine(ep).rotateZ(90), DrawLine(ep));
}

function DrawPlus0(ep)
{
    return union(DrawPlus(ep), Draw0(ep));
}

function AttachSide(ep)
{
    return union(
        AttachS().translate([-d1,-d1,0]),
        AttachS().translate([-d1,d1,0]),
        AttachF().mirroredZ().translate([d1,-d1,0]),
        AttachF().mirroredZ().translate([d1,d1,0])
        );
}

function Core()
{
    R2 = R/2; 
    
    return union(cube(R), 
    Attach(0).rotateX(90).translate([R2,0,R2]),
    Attach(0).rotateX(-90).translate([R2,R,R2]),
    Attach(0).rotateX(90).rotateZ(-90).translate([0,R2,R2]),
    Attach(0).rotateX(-90).rotateZ(-90).translate([R,R2,R2]),
    Attach(0).translate([R2,R2,R]));
}

function Side()
{
    return difference(cube([v+R,R,sideH]), Attach(epsilon_material).translate([R/2,R/2,0]));
}

function regular_side()
{
    return difference(Side(), 
        cube([epsilon_material, 2*R,2*R]),
        cube([2*R, epsilon_material,2*R]),
        cube([2*R, epsilon_material,2*R]).translate([0,R - epsilon_material, 0])
        );
}

function xor(a, b)
{
    return union(difference(a, b), difference(b, a))
}

function attach_side()
{
    return xor(regular_side(),AttachSide(epsilon_material).translate([R/2, R/2, sideH]));
}

function plain_top()
{
    R2 = R/2
    return difference(cube([R + 2 * v, R + 2 * v, topH]),  Attach(epsilon_material).translate([R2 + v,R2 + v,0]));
}

function BottomVanil()
{
    return union(cube([R + 2 * v, R + 2 * v, v]), Core().translate([v,v,v]));
}

function bottom_attach()
{
       return difference(BottomVanil(), Attach(epsilon_material).translate([R2 + v,R2 + v,0]));
}

function top_attach()
{
    return union(plain_top(),Attach(0).translate([R2 + v,R2 + v,topH]));
}

function top0()
{
   R2= R/2;
   return union(plain_top(), Draw0(0).translate([R2+v,R2+v,topH])); 
}

function top_plus()
{
   R2= R/2;
   return union(plain_top(), DrawPlus(0).translate([R2+v,R2+v,topH])); 
}

function bottom_plus()
{
   R2= R/2;
  return difference(BottomVanil(),DrawPlus(epsilon_material).translate([R2+v,R2+v,0])); 
    
}

function bottom0()
{
   R2= R/2;
  return difference(BottomVanil(),Draw0(epsilon_material).translate([R2+v,R2+v,0])); 
    
}

function bottom_plus0()
{
    return intersection(bottom_plus(), bottom0());
}

function all()
{
  return union(regular_side().setColor([0.2,0.9,0.5]), 
  attach_side().translate([0, 3*R, 0]).setColor([0.2,0.9,0.5]),
  plain_top().translate([3*R, 9*R, 0]).setColor([1,1,0]), 
  top_attach().translate([3*R, 0, 0]).setColor([1,1,0]), 
  top0().translate([3*R, 3*R, 0]).setColor([1,1,0]),
  top_plus().translate([3*R, 6*R, 0]).setColor([1,1,0]),
  bottom_attach().translate([6 * R, 0, 0]).setColor([0.9,0.5,0.5]),
  bottom_plus().translate([6 * R, 3*R, 0]).setColor([0.9,0.5,0.5]),
  bottom0().translate([6 * R, 6*R, 0]).setColor([0.9,0.5,0.5]),
  bottom_plus0().translate([6 * R, 9*R, 0]).setColor([0.9,0.5,0.5])
  //top_plus(),
  //bottom_plus(),
  //bottom_plus0()
  );  
}

function main() {
    
    //return AttachS();
    
    //for(var i=0; i<attach_m; i+=attach_w) {
    //    v = union(v, MainAttachMale().translate([i,0,0]));
    //}
    
//     m  = attach_m;
//    h = attach_h;
//    dp = attach_dp;
//    w = attach_w;
    //difference(union(cube([m, dp, h]), MainAttachFemale(), MainAttachFemale().mirroredX().translate([m, 0, 0])),cube([m, dp, h]).rotateX(-45)); 
    //return difference(union(cube([m, dp, h]), MainAttachFemale()),cube([m, dp, 2*h]).rotateX(-45));
    
   //return union(v, AttachEmale());
   //return AttachEfemale();
   return all().translate([-5*R, -5*R, 0]);
}

--------------

Regarding the empty space I was thinking about something a bit different. We know that empty space remains empty, so we can simulate only local environment of the action. This will in the larger scale create some interesting CA sculptures, probably similar to aluminium ant colonies just done by hands and tiles.

Another possible direction is actually a possible real implication to algorithmic self assembly.

Posted: **March 22nd, 2019, 11:00 am**

simsim314 wrote: Regarding the empty space I was thinking about something a bit different. We know that empty space remains empty, so we can simulate only local environment of the action. This will in the larger scale create some interesting CA sculptures, probably similar to aluminium ant colonies just done by hands and tiles.

That's a good point, though it could affect physical stability. My thoughts when I posted were a little half-baked, thinking about the fact that Critters conserves the number of live cells, and there would be a lot of repetition if I ever bought the necessary legos.

simsim314 wrote: Another possible direction is actually a possible real implication to algorithmic self assembly.

It's always been in the back of my mind with this. E.g., could you build macroscopic tiles that could be shaken into fitting together according to rules? I don't think it works very well, at least not in a reasonable time frame, but it's a thought. Of course, with molecules it does work. I'll have to read that CACM article. "Algorithmic self assembly" is a good way to explain it as science and not an obscure hobby.

Posted: **March 23rd, 2019, 8:53 am**

pcallahan wrote:That's a good point, though it could affect physical stability.

If this project will catch we will obviously need a designing tool - in which except of the assembly instruction we will need to provide layer by layer attachment instructions so that it will not fall down. Reminding a bit the supports in 3D printing. Except that in our case we control the slope of the tiles, so maybe just good attachment to the first layer will be enough to hold everything.

pcallahan wrote:could you build macroscopic tiles that could be shaken into fitting together according to rules? I don't think it works very well

This is the best I've seen yet.

Posted: **April 9th, 2019, 6:33 pm**

I've implemented binary adder in simplified manner which is not based on axioms.

It has three types of components:

(1) Platform: this is the game space, where you place the binary numbers.
(2) 0-1 Cubes: The numbers attached to the platform.
(3) 8 adder tiles: The tiles which enforce addition.

Use OpenJScad to view:

Code: Select all

epsilon_material = 0.03;
depth_factor = 0.6;
symbolR_factor = 0.5; 
sumbolH_factor = 0.12;
symbolW_factor = 0.3;
r_factor = 0.1;
    
R = 10; //The length of cube
v = 0;
d1 = 2.75;
d2 = 3;

h_extrusion = v * depth_factor;
sH = R * sumbolH_factor;
sR = R * symbolR_factor * 0.5;
sW = (1 - symbolW_factor) * sR; 
sWcube = symbolW_factor * sR; 
TileH = R * 0.35;

function Draw0(ep)
{
   l = (sR - sW)/2 + ep; 
   u = (sR + sW)/2; 
   
   return union(rotate_extrude( polygon({points:[ [u-l,0],[u+l,0],[u,l]]}) ).translate([0,0,sH+ep]),
    difference(cylinder({r:(sR + ep), h:(sH + ep)}), cylinder({r:(sW - ep), h:(sH + ep)})));
    
}

function DrawLine(ep)
{
   sWc = sWcube * 2;
   sw2 = sWc / 2;
   s1R = sR;
   s1H = sH / 2; 
   
   var p = polygon({points:[ [-sw2-ep,0],[sw2+ep,0],[0,sw2+ep]]});
   var exp = linear_extrude({ height: 2*s1R + 2 * ep }, p).translate([0,s1H+ep,-s1R-ep]);
   
   return union(cube([2*s1R+2*ep, sWc + 2 * ep, s1H+ep]).translate([-s1R-ep, -(sWc)/2-ep, 0]),
                 exp.rotateX(90).rotateZ(90));
}

function draw0_cube()
{
  return difference(union(Draw0(0).translate([R/2,R/2,R]), cube(R), cylinder({r: R * r_factor, h:(R)}).translate([0, R/2, 0])), union(Draw0(epsilon_material).translate([R/2,R/2,0]), cylinder({r: R * r_factor + epsilon_material, h:(R)}).translate([R, R/2, 0])));
}

function draw1_cube()
{
    return difference(union(DrawLine(0).translate([R/2,R/2,R]), cube(R), cylinder({r: R * r_factor, h:(R)}).translate([0, R/2, 0])), union(Draw0(epsilon_material).translate([R/2,R/2,0]), cylinder({r: R * r_factor + epsilon_material, h:(R)}).translate([R, R/2, 0])));
}

function draw_platform()
{
    ep = epsilon_material;
    realR = R + ep; 
    N = 8;
    PlatH = R * 0.2; 
    H = PlatH + realR + TileH + 2 * ep;
    PlatW = R / 3;
    
    v =  cube([2 * realR, N * realR, PlatH ]);
    
    for(var i=0; i<N; i+=1) {
            v = union(v, Draw0(0).translate([R/2 ,R/2 + i * realR, PlatH]));
    		v = union(v, Draw0(0).translate([R/2 + 2*ep + realR, R/2 + i * realR, PlatH]));
        }
        
    return union(v.translate([0,PlatW,0]), cube([2 * realR, PlatW,H]), cylinder({r: R * r_factor, h:(H)}).translate([R/2 + ep, PlatW, 0]),  cylinder({r: R * r_factor, h:(H)}).translate([R/2 + ep + realR, PlatW, 0]));
}

function add_inputs(v, i1, i2)
{
    ep = epsilon_material;
    realR = R + ep; 
     
    if(i1 == 0)
        v = difference(v, Draw0(ep).translate([R/2 ,R/2, 0]));
    else 
        v = difference(v, DrawLine(ep).translate([R/2 ,R/2, 0]));
        
    if(i2 == 0)
        v = difference(v, Draw0(ep).translate([R/2 + 2*ep ,R/2+realR, 0]));
    else
        v = difference(v, DrawLine(ep).translate([R/2 + 2*ep ,R/2+realR, 0]));
        
    return v; 
}

function add_output(v, o)
{
    if(o == 0)
        return union(v, Draw0(ep).translate([R/2 ,R, TileH]))    
    else
        return union(v, DrawLine(ep).translate([R/2 ,R, TileH]))    
}

function add_input_c(v, c)
{
	ep = epsilon_material;
	if(c == 0)
		return difference(v, union(cylinder({r: R * r_factor + ep, h:(R)}).translate([0, R/2, 0]), cylinder({r: R * r_factor + ep, h:(R)}).translate([0, R/2 + realR + ep, 0])));
	else 
		return difference(v, cylinder({r: R * r_factor * 1.5 + ep, h:(R)}).translate([0, R, 0]));
	
}

function add_output_c(v, c)
{
	ep = epsilon_material;
	if(c === 0)
		return union(v, union(cylinder({r: R * r_factor + ep, h:(TileH)}).translate([R, R/2, 0]), cylinder({r: R * r_factor + ep, h:(TileH)}).translate([R, R/2 + realR + ep, 0])));
	else 
		return union(v, cylinder({r: R * r_factor * 1.5 + ep, h:(TileH)}).translate([R, R, 0]));
	
}

function add_tile(i1, i2, ci, co, o)
{
    ep = epsilon_material;
    realR = R + ep; 
    v = cube([R, 2 * realR, TileH]);
    v = add_inputs(v, i1, i2);
    v = add_output(v, o);
    v = add_input_c(v, ci)
    return add_output_c(v, co);
}

//Platform - 1 √
//0-1 blocks - 2 √
//8 tiles to add - 8 

function main () {
//return union(draw1_cube(), draw0_cube().translate([2*R, 0,0]));
//platform 
R3 = R * 3; 
R6 = R * 6; 
//return ;
return union(
    add_tile(0,0,0,0,0),
    add_tile(1,0,0,0,1).translate([R3, 0, 0]),
    add_tile(0,1,0,0,1).translate([R6, 0, 0]),
    add_tile(0,0,1,0,1).translate([0, R3, 0]),
    add_tile(1,1,0,1,0).translate([R3, R3, 0]),
    add_tile(1,0,1,1,0).translate([R6, R3, 0]),
    add_tile(0,1,1,1,0).translate([R3, R6, 0]),
    add_tile(1,1,1,1,1).translate([R6, R6, 0]),
    draw_platform().translate([R*8, 0, 0]),
    draw1_cube().translate([-R3, 0, 0]), draw0_cube().translate([-R3, R3, 0])
    );
}

Posted: **April 2nd, 2024, 11:32 am**

I finally made a set of Margolus Critters tiles using a 3D printer. I have been putting off the extensive write-up I plan, but I'm awaiting warranty repairs on the printer right now, so this might be a good time to explain more and make less plastic junk. I'll just give this teaser for now:

: 20240402_080139.jpg (1.99 MiB) Viewed 60697 times

There are 6 distinct tiles up to rotations and they are shown in the lower right, top and bottom faces. I've been consistent in turning them. You can think of the pairs as mirror images across the vertical axis. The bump in the middle and the clipped corners enforce the diagonal shift between layers. They don't work quite as well as I'd like, but they do snap together and hold.

Posted: **April 7th, 2024, 4:51 pm**

Note: I corrected the picture, which had steps 1 and 3 swapped. I also highlighted the live cells.

I finally put together the 4 phases of a moving critter glider and took pictures. This shows the steps as a composite, and I have also altered the images to correct for perspective. The glider moves up one tile position (2 cell positions) after 4 phases. I am using the uniform rule in which empty cells (vacuum) alternates, shown as o and + on these tiles.

: critters2.png (800.09 KiB) Viewed 60638 times

The non-alternative rule could be implemented but could use up to 12 distinct tiles instead of 6 (but maybe that can be reduced).

Posted: **April 8th, 2024, 11:34 pm**

Finally, I wrote this up and created a Printables for it: https://www.printables.com/model/837487 ... le-cellula

ConwayLife.com

Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling

Re: Realizing CGOL a 3d tiling