Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I'm interested in tilings of the plane by squares, with labels on the edges. It's well known that (1) the question "can one tile the plane with the following finite set of tiles?" is undecidable, and (2) there are finite sets of tiles that tile the plane, but only aperiodically. Also, (1) implies (2).

Is the question "can one tile the plane periodically with the following finite set of tiles?" decidable?

share|improve this question
    
By periodic, do you mean periodic in both directions? –  Joel David Hamkins Feb 11 '13 at 15:02
    
The tilability question is undecidable even if we restrict the tiles to be rectangles. –  Gjergji Zaimi Feb 11 '13 at 16:16
    
My question was whether it would count as periodic if the pattern repeats only in the horizontal direction, but the columns are not periodic vertically. I assume not. If periodic in both directions, then you can assume period is the same via least-common-multiple. –  Joel David Hamkins Feb 11 '13 at 16:20
    
@Joel: both questions are valid. I'm interested in understanding the current status, so extra restrictions are also welcome: periodic in one or two directions; or require deterministic tiles (for every corner, horizontal and vertical label, there exists at most 1 tile with these labels in that corner). I'll vote you up if nobody comes up with a complete argument within a few days :) –  grok Feb 13 '13 at 3:21
add comment

1 Answer

up vote 7 down vote accepted

The answer appears to be no.

Consider first the case of the anchor-tile periodic tiling problem, where we insist that a particular anchor tile is used. Let's modify the usual Wang tile argument, due to Berger, for the oringal tiling problem. That argument shows that for any Turing machine program $p$, we can create a set of Wang tile types (square tiles with labels on the edges, to be matched up in a tiling) such that the operation of program $p$ corresponds directly to the pattern of tiles appearing in any tiling. Basically, the anchor row displays a complete picture of the Turing machine in the start configuration, and each subsequent row shows the configuraton after one additional step of computation using program $p$. The main idea of the scheme is that the tiling can continue as long as the program keeps running, and so there is a tiling if and only if the program does not halt. This is why the original anchor tiling problem is undecidable. (And the anchor feature was removed by a separate argument.)

But essentially the same idea can be used to solve your problem. We can modify the tiles involving the halt state so that a halting computation will support a periodic tiling. Basically, what is needed are tiles that will lead from a tile on which the program has halted to transform the next row to the initial configuration again. It would be a detailed thing to check, but after one has spent time using these Wang tiles to simulate Turing machine computations, this seems to be easily handled in the same way.

The end situation will be that if $p$ halts, then there will be a periodic tiling using the desired anchor tile, and if $p$ does not halt, then there will be no periodic tiling using that anchor tile. So the question will be undecidable.

Finally, it seems to me that one can remove the anchor tile requirement in the same way that is done with the original Wang tile argument (but this is a complication).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.