Registered: Aug 2003
Posts: 712

A PhD student named Paul Harrison has an interesting program that looks for ways of assembling complex tiles. He found a set of tiles that effectively emulate rule 110, among other things. His website can be found here -

http://www.logarithmic.net/pfh/ghost-diagrams

A brief "abstract" -

Ghost Diagrams is a program that takes sets of tiles and tries to find patterns into which they may be formed. The patterns it finds when given randomly chosen tiles are often surprising.

It turns out that tiling patterns are a form of computation of equal power to Turing machines, lambda calculus, and cellular automata. For example, here is a tileset implementing "Rule 110", a cellular automaton known to be capable of universal computation.

Report this post to a moderator | IP: Logged

Registered: Sep 2005
Posts: 2

Thanks for linking to me. :-)

Here are some more screenshots:

http://www.logarithmic.net/pfh/ghos...ams/screenshots


With regards simulating cellular automata, there's a few interesting things about tile sets. Cellular automata are deterministic causal systems, whereas tile sets are non-causal constraint systems. So a tile set simulation of a cellular automaton not only encodes the rules of the automaton, but also the fact that it is deterministic causal.

This means (though I haven't followed this up in detail) one can think about tile sets that are "nearly" deterministic causal. One can add two tiles for a particular context, yielding a non-deterministic cellular automaton. Or one can omit a tile for a certain context entirely, so that any resultant assemblages can be seen as runs of a cellular automaton that "just happen to" never produce that particular context.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

Yes, I notice that. Legal constructions in a constraint system are in general "multiway".

I've been looking at various modified NKS systems that incorporate "underdetermined" transitions for independent reasons. A CA with one random output case in its rule table is the simplest example - multiple evolutions are possible from a given initial. Or you can consider a "machine with input" CA or ICA, that switches its rule at each step according to an external sequence. If the rules is switches among, differ only in a single case in their rule table, effectively you are determining the outcome of that case according to an external sequence. If that sequence is random it behaves much like the previous. But you can also manipulate the application order to maximize this or minimize that e.g.

I take your point about Wolfram on constraint systems, that the difficulty of satisfying complicated constraints is not in itself a reason not to look at constraint systems. It is a reason not to expect most natural cases of complexity to be caused by specific, "only this works", satisfaction of multiple constraints. But he also found it was relatively easy to get iterated schemes to approach constraint satisfaction without reaching it. He focused less on constraints so easy to satisfy, that large sets of possible patterns are compatible with the constraints. Although he considered something similar later as multi-way systems.

This suggests a couple of additional things you might look at. One, you might look at the variety of typical patterns produce by your tile sets, without the absolute preference for single choice moves or the closest to the center criterion, and without searching for a tiling. Just, if tiles with these edges are thrown together making possible legal moves, what sort of (potentially tangled rather than tiled) shapes result? When you've seen an instance, keep it in a list that you won't stop when you find, and will backtrack from if you get stuck without finding a new pattern. For a given tile set, then ask, what are the first n (limited size) patterns found this way? In other words, just typical evolutions in tile-growth space, without "trying" to get an X-ee or a Y-ee anything. Empirically, the idea is such shapes would arise naturally from a soup of such fitted parts.

Two, you might look at the shapes you find internally with the existing algorithm, but from which you have to backtrack as things are now. Find large shapes that eventually "get stuck" or "don't fit" somewhere. These would be analogs of approaching constraint satisfaction without actually doing so. Empirically, one might think of this is trying to minimize some energy and getting enough of the system into a state that does, with bits sticking out that fail to, but that are energetically less "expensive" than the gain from the rest of the shape.

I should also say I see real aesthetic potential here. I particularly liked your Celtic knots, for example.

Report this post to a moderator | IP: Logged

Registered: Sep 2005
Posts: 2

My suspicion is that there are constraint systems that can reach full satisfaction in "near" linear time, eg O(n log n) or O(n^2). Part of the algorithm in "Ghost Diagrams" is to randomly backtrack when it gets stuck. The amount backtracked is usually small, but sometimes quite large -- a scale free distribution, in fact. There are a number of tile sets that can be assembled in reasonable time using this strategy, but not with backtracking of more uniform size. Such patterns are often the most visually interesting, too.

I also think there might be physically plausible analogues of this at a molecular level. Imagine a soup of molecules having scale free distribution of sizes, thus impacting each other with a scale-free distribution of forces and knocking a scale free distribution of sizes of chunks off each other. Or somesuch.

The current Ghost Diagram algorithm can be seen as a simulation of this where "chunk getting knocked off" events are much rarer than "tile being added" events.

Report this post to a moderator | IP: Logged

Registered: Aug 2003
Posts: 712

I understand the algorithm and it is a good one for search, because anything stuck with small jostles will eventually chance upon a large one and shake out of that pathway. But I don't find it all that realistic, physically. It is much more likely the jostle scale is bounded above, a function of temperature e.g. Which means a lot more real world semi-patterns will arise in the various "stuck" configurations, rather than continually shaking harder until they find a path to a perfect fit. It is good search programming but not plausible as self assembly, at least in most cases.

I think the less perfect patterns encountered along the way would be interesting in their own right, however. I encourage you to look at some of them. The perfected patterns are neat and one can imagine deliberately engineering them by mimicking your procedure. But the imperfect ones that would be created by bounded-scale backtracking would also be interesting. Try treating the backtracking as a model parameter, and see what sorts of patterns you get with none, with backtracking only a single step, with backtracking 1-3 steps with a damped distribution (something as simple as {1,1,1,1,2,2,3} would work fine), and compare the result to scale free backtracking.

Programmatically, put in a modular subroutine at that step and let it depend on a global parameter. Then do runs - from this set of allowed tiles, here are some shapes that arise with no backtracking, with backtracking 1, with backtracking 1-3 damped, with scale free backtracking. I am sure the results would be interesting. The point generalizes. To understand the impact of a given step in an algorithm on the overall behaviors seen, one does "sensitivity analysis" on that step.

Report this post to a moderator | IP: Logged