Can the computer be able to design a non-periodic tiling?

Question

Non-periodic tiling is an interesting topics in geometry and beyond. PT (Penrose Tiling) is a famous example of non-periodic tiling.

Rogers Penrose once said that the computer will stumble when trying to solve the problem whether PT can tile the entire plane. This is because for the computer to solve this problem, either it has to make up a pattern that is periodic or to run forever to prove computationally the plane is covered by PT. And in both cases, this will be impossible.

Does it mean there is no way for the computer to design a non-periodic tiling, in particularly, using one shape? Non-periodic tiling using one shape is known as einstein problem.

If the computer can make it, it means it may fall into contradiction, given the Penrose argument above. This means only human is able to design a non-periodic pattern, or isn`t?

Answer 1

You said:

My question is whether designing a non-periodic tiling is computable.

The answer is yes, absolutely. The 1966 construction of Robert Berger produces an infinite family of aperiodic tile-sets. (That is, each of the tile sets it constructs will tile the plane, but none of them will tile it periodically.)

The method goes like this:

1. Pick a recursive language and construct a Turing machine that decides it. This machine will halt on all possible inputs.

2. Use Berger's construction to translate the machine into an aperiodic tile set.

Each infinite row of tiles represents one state of the machine's execution, including its infinite tape, its current head position and internal state.

The row with $y=0$ represents the initial execution state, and the tiles can be constructed so that this row can only be extended to infinity in ways that actually represent a real execution state. For example, a subset of the tiles will be special tiles that mean “the tape head is at this location”, and the tile set can be constructed so that every infinite row of tiles must include exactly one of these special tiles.

The tiles are constructed so that an adjacent row of tiles must then represent the next complete execution state. This extends to a covering of the upper half-plane. It is periodic only if the execution falls into an infinite loop. But since, by construction, the original Turing machine is known to halt on all inputs, this is impossible.

(The compactness theorem can be used to show that any tiling that covers the half-plane can be extended to cover the whole plane, so this detail can be ignored.)

The tiles are usually expressed as colored squares, where adjacent colors must match; these are called “Wang tiles”. But it is easy to convert Wang tiles into uncolored squares with wiggly edges that fit together like jigsaw puzzle pieces, making the constructed tiles purely geometric.

We can turn the Berger construction around: given a tile-set, can we decide whether it will tile the plane periodically? No, because by Rice's theorem we know that it is undecidable whether a given Turing machine goes into an infinite loop on every possible input.

Of course this does nothing to help decide whether a particular set of shapes has a periodic tiling, or an aperiodic tiling, or even any tiling at all. But as you said, your question was whether designing a non-periodic tiling is computable, and the answer to this question is definitively yes.

Answer 2

The issue with this question is what "designing" is supposed to mean. There are at least four aspects to it:

1. Can an aperiodic tile-set be computably generated?

2. Can an algorithm be found to tile the plane for a particular (e.g. the Penrose or any einstein) aperiodic tile-set?

3. Could a computably generated aperiodic tile-set be proven to be aperiodic by a computer?

4. Must some aperiodic tile-sets be non-computably generated? In particular could the einstein tile-set be only non-computably generated, perhaps because it would be some kind of fractal?

To answer the first part, we have the 11 Wang tiles in the upper right of the WP article (https://en.wikipedia.org/wiki/Wang_tile) : aperiodic and computably generated. So yes aperiodic tiles can be computably generated.

To answer the second part there are also algorithms for tiling the plane for some of these examples of aperiodic tile-sets. So is there always such an algorithm? The answer to this has to be "no". The analogous problem for Turing Machines is that there are algorithms for solving the Halting problem for some Turing Machines, but no such algorithms exist in general (that is no universal algorithm exists).

In the third part we are asking whether given that a computer has generated an aperiodic set, it can actually prove that it is aperiodic. Now the point of the Penrose argument was that in this case the computer was considered as trying to determine this by actually trying to do the tiling. Since this is an aperiodic example, the fact that it is aperiodic is not determinable by finite computer experiment (unlike in the periodic case). [In the periodic case, the computer could try larger and larger rectangles and for each rectangle find by trying all cases whether that rectangle could be covered by the tiles or not. If not then no covering is possible. If it can be covered, then a check can be made against the edges of the rectangle to see whether they match. If so this is a periodic tiling, with the discovered period, which can be extended trivially by the computer indefinitely across the plane.]

There is though a subtlety in the argument here, which is where some of the controversy connected with the wider Penrose-Godel argument might arise. The point is easier to see with the argument made in the previous section of the linked video. Here he points out that computers cannot prove that multiplication by ordinary numbers is commutative. The reason is that they would have to check every number pair. However logicians would not accept that "arithmetic commutativity is non-computable".

So in the tiling case, the Penrose argument would be that if a proof of aperiodicity exists, then it uses axioms (describing "insights" into tiling) which the computer cannot work out for itself. However a logician would correctly say that the given proof was computable given its axioms.

So it depends on what "designs" means in the original question, to further the answer.