One way to tile the plane with Wang tiles

Friday, February 20, 2015

tl;dr Backtracking Wang Tiler and it's pretty to watch go.

You're probably familiar with tesselations. Tilings, that is. A Cartesian grid tiles a plane with squares, a honeycomb tiles a plane with hexagons, and so forth. There are lots of examples. But the most interesting tilings, to me, are aperiodic ones — tilings that are not regular. Similar-looking sections of them may repeat, but the tiling as a whole never repeats exactly.

The most well-known example is probably Roger Penrose's kite-and-dart construction. But, as is often the case, the most famous example was not the first. The foundational work on aperiodic tilings was done years earlier, by Hao Wang, who came up with the concept, and posed the question (I'm paraphrasing):

Given a set of tiles, is there an algorithm that tells if they tile the plane aperiodically or not?

In other words, is the set of aperiodic tilings decidable? And Berger proved that it was not, by reducing it to the Halting Problem for Turing machines. Each aperiodic tiling can be put into one-to-one correspondence with a Turing machine that never halts.

That suggests that aperiodic tilings are tricky business, indeed.

But to be clear, this is a general question about arbitrary sets of tiles. Once you have picked a set of tiles, you may well prove it is aperiodic, and you may well tile the plane with them.

Of course, that business is still a little tricky. You can certainly work out an aperiodic tiling by hand, using human ingenuity and trial and error. Can you instruct a computer to do it? Yes, although unsurprisingly it leans a bit more on the trial and error side.

But wait — if a tiling corresponds to a Turing machine that never halts, how can you write a program for it? Ah, red herring — you just write a program that never quits. (Indeed, if you want to tile the "entire" infinite plane, what choice do you have?) But note that, technically, this might not be an algorithm, because algorithms are generally defined to terminate and produce a result. But we can put off that inevitable semantic debate by just avoiding that term.

At any rate, the process I've used is:

  • Select tiles randomly and place them in a spiral, so that new tiles are always adjacent to existing tiles. (Except the first one, of course.)
  • If at any point you find you can't place a new tile along the spiral, because it doesn't match any of the existing tiles, then backtrack — erase the previous tile you placed, try another possibility for that position chosen at random, and continue again from there.

I'm not claiming this is efficient! It ain't, not by a long shot. But it's correct — it will tile the plane "eventually", as long as the set of tiles permit tiling (whether periodic or aperiodic) — and it can be pretty to watch go.

It's also apparent that "spiral" and "backtrack" are incidental; it's just nicely linear to arrange it this way, but you should be able to accrete random clumps too. Which might be even more inefficient, but even prettier to watch go. Dunno, would have to try it, and I haven't yet.

One slightly interesting thing about the implementation is that the backtracking is not implemented the obvious way, with recursion, because we want to display the state of the tiling as we go along, and Javascript in a web browser in particular won't allow that; it won't update the display until the current computation is finished and it's ready to handle a new event.

Therefore, backtracking is implemented with what are essentially continuations. All of the alternate, untried possibilities for each position are stored along with every tile, as it is placed. To be sure, this is not a general-purpose continuation, but it does encapsulate all the pertinent data for the tiling process — data that would otherwise be embedded in the function call stack, and not accessible to us.

The implementation is also in the public domain, so if you want to hack on it, feel free. It resides in the Wang Tilers repository on Github, in which you can also find further documentation on it. And maybe, in the future, other implementations and/or other tiling strategies.

Since this announcement has already gotten quite long, maybe I'll cap it off with an interesting question.

There are, as I understand it, Wang tilings which aren't even computable: they correspond to Turing machines for which there is no computable method to generate them. (They never halt, but we can't prove this.)

However, this automaton we got here operates randomly. The implementation is pseudo-random, to be true, but let's assume this is just an approximation of an idealized automaton with genuinely randomized tiling choices.

In a sense, it is always trying to find a non-terminating Turing machine. If the current tiling it's trying to lay down doesn't work (= represents a Turing machine which halts,) it backtracks and tries a different randomly-chosen tiling until it finds a a tiling that does work (= represents a Turing machine that doesn't halt.)

If left to run forever, might this automaton generate a non-computable never-halting Turing machine, in the guise of a Wang tiling?

Perhaps I misunderstand it, but I think it could. Just because you can't computationally generate such a Turing machine, doesn't mean that taking the limit of an infinite random sequence couldn't yield such a thing. Certainly, the closure of all such tilings would include these, and I can't see what's stopping this automaton from "accidentally" picking one.

Of course, taking the limit of an infinite random sequence could be a philosophically troubling concept — perhaps as philosophically troubling as generating an uncomputable object.

After all, if your tiling does tile the plane, you've proved the corresponding Turing machine does indeed never halt.

But it's hard to see how you'd know your tiling does tile the plane, without first knowing that the Turing machine does not halt.

Perhaps questions about infinity are best saved for people who have an awful lot of time on their hands.