Warren, Some of these replies are in a different order to how you sent them:

this code finds all possible decorated trunc-octs.

In three dimensions, a tile (probably a cube will suffice) can have helical protrusions from each face, like so: http://cp4space.files.wordpress.com/2013/08/helical.png If we have similar helical passageways cut into the cube, then they could pass through several cubes. The upshot of this is that we can turn any (possibly disconnected) decorated cube into a connected one, enabling non-adjacent matching rules. (This was how I made a hexagonal lego prism emulate the TS tile.) So, the only real issue is to find local matching rules capable of forcing a three-dimensional recursive pattern. We know (a la Taylor-Socolar) that this can be done in two dimensions, so surely we can get a non-trivial three-dimensional variant...? Indeed, can the modified Sierpinski triangle pattern of the T-S tile be generalised to a tetrahedral pattern?

You would probably immediately think of Conway "life" as a good candidate, but I suspect not since it needs access to all 8 neighbors of a square. Would be better to find a 2D CA with, e.g, the lattice of square-centers alternating in time with the lattice of square-corners (in 3D this is the BCC lattice, whose Voronoi region is the truncated octahedron, 24 possible rotations) where each state is a function of its 4 predecessors. Larger alphabet than {0,1} perhaps.

Okay, this is worryingly coincidental after I posted this (about five hours before your message): http://cp4space.wordpress.com/2013/08/25/block-cellular-automata/ My motivation for considering BCC automata was to create a replicator in CGoL, which emulates an arbitrary 16-state BCC automaton, which can in turn emulate CGoL itself. The hardware is much simpler for BCC automata than full Moore-neighbourhood cellular automata. Conway's Game of Life can be emulated by a BCC automaton with 16 states (by grouping the cells into 2x2 clusters) as a first estimate. I sent this e-mail to Andy Adamatzky in June 2010:

[beginquote]

Recent advances in DNA nanotechnology have led to the ability to implement Wang tiles (a tiling system with computational properties). Similar to Penrose tiles, Wang tiles can enforce complex, aperiodic patterns.

One of the more interesting patterns created automatically by DNA tilings is a Sierpinski gasket, formed by emulating the XOR rule (the simplest non-trivial cellular automaton, similar to Rule 90).

This gave me an idea: can a tiling system simulate Conway's Life?

An important stepping-stone to producing a set of Life-simulating tiles is a 16-state cellular automaton by Paul Callahan. He originally used it to accelerate his Life program.

Each cell has 16 states, and corresponds to a 2x2 block of Life cells. Four of these blocks in a square (4x4 Life cells) determine the state of the central 2x2 block in the following generation. So, we effectively have a 16-state cellular automaton, where each cell depends on four cells in the previous generation.

An interesting thing to note is that the cells do not stay in one place: alternate generations have cells offset by ½-units. In other words, the lattice for generation 1 is the dual tiling of the lattice for generation 0.

Plotting the cells in 3D space (two spatial, one temporal dimension) results in the body-centred cubic (BCC) lattice. The Voronoi cells are truncated octahedra, so these are what we use as the 'Wang tiles'. For convenience, we consider the vertical dimension to be the temporal one, with each generation above the previous one.

It is clear to see that each truncated octahedron shares a hexagonal face with each of the four cells below it (the four cells which affect the cell in question). It also shares a hexagonal face with each of the four cells above it (those which it directly affects).

The square faces of the truncated octahedra can be indented or raised to enforce the orientation of the cells. The eight hexagonal faces are more interesting, and correspond to the generation rules for Life. There is one Wang tile for each possible neighbourhood (65536 in total), and the lower four hexagons are unique to that particular tile. The upper four hexagons correspond to the next state of the cell.

Each of the lower four hexagons have between zero and fifteen bumps; each of the upper four hexagons have between zero and fifteen indentations.

For example, the central 2x2 block of the neighbourhood:

.o.o .oo. ..o. ....

becomes:

o. oo

in the next generation. In the 16-state cellular automaton, this is equivalent to the rule:

5|6 ----> 11 0|8

(The numbers are the binary interpretations of the 2x2 blocks of Life cells.)

So, the truncated octahedron corresponding to this particular neighbourhood will have 5, 6, 8, and 0 bumps on the lower four hexagons, numbering in a clockwise fashion, and 11 indentations on each of the upper four hexagons. There are another 65535 truncated octahedra, one for each of the 4x4 Life neighbourhoods.

By placing a single layer of these truncated octahedra on the bottom of a container, and placing tiles according to the matching rules, this will simulate Conway's Game of Life. The structure formed by the truncated octahedra is found in some crystals, and was conjectured by Lord Kelvin (William Thomson) to be the optimal foam of soap bubbles. It has the highest symmetry group of any three-dimensional structure, and is the best lattice covering of spheres in three dimensions.

http://en.wikipedia.org/wiki/Bitruncated_cubic_honeycomb

[endquote]

By being only slightly cleverer, CGoL can be emulated as a 9-state BCC automaton.

...

Yes. In the same way that the Taylor-Socolar tile is a decorated hexagon, I suspect that there is a decorated rhombic dodecahedron  or decorated truncated octahedron capable of tiling space strongly aperiodically.

 --great minds think alike again :). Furthermore, even a plain decorated hypercube likely works in high enough dimension.

I can believe that.

And in 4D, the 24-cell is the obvious candidate for decoration and I strongly suspect the 24-cell is good enough to do the job (if we were smart enough to see precisely how).

Hmm, yes. Let's see: it has an automorphism group of order 24*48, and its rotational subgroup would be half of this, so 576. This is rather promising.

An even cooler goal than mere "strong aperiodicity" (which is highly related) is "Turing universality." Berger somehow proved 2D Wang tiling undecidable. I'm not sure exactly how he did it. But vaguely the idea is, let X=space and Y=time; then the history of a Turing machine (head+tape), is the tiling in the XY plane: Tiles if and only if Turing machine does not halt. But that idea runs into the obstacles that (1) this would only be a quarterplane (or region of similar ilk) being tiled not the full plane, (2) it would only prove extensibility of some initial state (the tiles touching the X-axis) is undecidable, not "tiling in any way at all." Berger somehow overcame those obstacles.

Yes, I've got a copy of Grünbaum and Shephard's `Tilings and Patterns', which gives details (I believe).

Incidentally the "does it tile periodically" problem is decidable, noted by Hao Wang, and this result is easy.

Of course, a "K-1 dimensional Turing universal cellular automaton" seems more natural starting point than "a Turing machine."

Agreed.

Jarkko Kari in 1990 showed (related to the tiling problem by Wang tile) that the "is your 2D or 3D CA reversible" problem is undecidable.

Matthew Cook has the simplest 1D UTM,  http://en.wikipedia.org/wiki/Rule_110_cellular_automaton I'm pretty sure the rule-110 automaton can be implemented in "2 and a half" dimensions using 2 (or perhaps 3) kinds of tiles and max packing density criterion not true tiling. That is, the question "can a 3X1sidedinfinityX2sidedinfinity slab be filled with these 2-3 tile types at packing density>0.99, given that the tiles touching the 2sidedinfinite face are specified (specification finite since infinite repeating patterns plus finite stretch disagreeing with it)?" is Turing undecidable. If grant me 1 extra kind of tile, I can fill in the holes with it to make the true-tiling question undecidable. You can probably figure out the details yourself of how to do that.

You know about all that sort of stuff.

So somehow you'd have to computer search the finite space

Infinite, by the helical decoration idea. :)

of trunc-oct decorations, to find one which yielded Turing universal power. How the hell to do that? See below for ideas.

Another issue with "life" and rule-110 is this. If you have only 1 tile type, I think the only CAs you can implement are "reversible" CAs (both life and 110 are not). Information-erasing many-to-1 irreversible transitions seem impossible.

I'm not completely convinced. We already know that CGoL can be emulated with ... hmm ... 9^4 = 6561 Wang truncated octahedra. So, presumably the issue is that you're only allowed one tile? However, is it not conceivable that a single monomer can be composed in different ways to yield multiple meta-tiles?

We can however consider CAs with certain forbidden transitions corresponding to positions where no tile can be placed. That is a larger class than "CAs." Something like that is unfortunately probably what is needed.

Also note, a trunc-oct can actually "see thru" the 2D layer at time t-1 to also access its immediate predecessor at time t-2, giving you a bit more power than a plain CA.

Indeed. This is rendered obsolete by the helical decoration idea, though.

If we refuse to decorate the 6 square faces and only decorate the 8 hex faces, then it'd be a plain CA, the t-2 trick would be unused. Note with this un-use, that every initial state (2D layer) would be possible since neighboring truncocts in a single t=const layer do not touch hexes, only touch square faces. That's very nice, so I'd recommend the un-use strategy.

I actually suspect that there is some decoration of tiles such that, given an initial layer at t=0 the question "can the next layer at t=1 exist?" is undecidable.

Most probably.

The few surviving tile types -- the ones that actually implement 2D CAs -- could then be checked by Wolfram's type-classification for random initial data to see which seemed to be candidates for Turing power. This too should be largely automatable. You'd then have to stare at the results and exercise the grey cells a lot to figure out what was what.

Yes, you can depth-first search for periodic tilings, and for impossible tilings. If we dovetail this process over all candidate tiles, the boring ones (periodic or impossible) will be eliminated soon, and the ones that survive could be subjected to human analysis.

...

As long as you don't allow both enantiomorphs of a tile, you can replace colour-matching rules with indentations and protrustions. --yes.

So anyhow, above I have outlined ideas for a computer-aided search procedure which has a decent shot at finding a 3D einstein with universal Turing power and/or mere forced-aperiodicity (the latter should be easier to prove).

Yes. Again, it's easier to eliminate boring examples than to search specifically for interesting examples.

I think some such search should be tried. Think one could find interesting results with it, even if not solve einstein problem.

Indeed. This might be conceivably applicable to self-assembling (nano?) technology. There's a thesis by Toth-Fejel about this sort of thing, possibly entitled `Kinematic Self-Replicating Machines'. Sincerely, Adam P. Goucher