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

Anyone experienced with the undecidability of aperiodic tiling?

It's related to the halting problem which Turing proved was undecidable in the 30's and basically superimposes tiles onto other tiles which can be used to construct a Turing machine which would tile the plane aperiodically.

The proof given in Robinson (see below) shows that because you can construct such a machine the tiling problem is equal to the halting problem and therefore undecidable. I follow this through the paper and feel I understand the conclusion.

The problem is my girlfriend says this is all fine but only works for hierarchical tilings. I say well all aperiodic tiles are hierarchical and she says prove it.

Problem is I can't so I think I'm reading the proof wrong.

The paper is here

http://lipn.univ-paris13.fr/~fernique/qc/robinson.pdf

share|improve this question
    
I don't understand what "only works for hierarchical tilings" means. Let's say we've agreed on what it means for a set of tiles to be "hierarchical". The proof reduces the halting problem to the tiling problem. Do you want a reduction of the halting problem to "the tiling problem for non-hierarchical tile sets"? –  Anton Malyshev Jan 7 at 23:55
    
The proof, as I understand it, reduces the halting problem to the tiling problem by specifying that the Turing machine runs within one of the finite sized "red borders" which can be infinitely large. If no such hierarchical structure exists, that is to say no set of borders (of some shape or form) of increasing size can be constructed, then over what space would the Turing machine be running? Cont... –  Scott C Jan 8 at 0:26
    
Assuming that the tiling problem is in fact undecidable, then there must exist aperiodic tile sets for which there is no way to prove their aperiodicity therefore clearly not all aperiodic tile sets have this hierarchical structure, else the problem would be decidable. We are aware she is wrong but we need to know why. –  Scott C Jan 8 at 0:30
    
Say A is the collection of tile sets which don't tile the plane periodically, and T is the collection of tile sets which tile the plane. The set of aperiodic tile sets is their intersection, AT. You're right: the argument in the paper can be used to show that there are tile sets which belong to AT, but we can't prove they belong to AT. However, it's still possible that all tile sets in AT are hierarchical, and that for each of them we can prove it belongs to A. It's just that there are some which we can't prove belong to T. In other words, AT is not recursively enumerable, but perhaps A is. –  Anton Malyshev Jan 8 at 2:13
1  
I am confused by the question. Is the word "hierarchical" being used here with a precise mathematical meaning? –  Joel David Hamkins Jan 8 at 4:18

1 Answer 1

It sounds like you're misunderstanding the proof: the main theorem is

There is a computable function $f$ (such things are in general called many-one reductions) from $\mathbb{N}$ to $\{$finite sets of tiles$\}$ (construed appropriately) such that $\Phi_e(e)\uparrow$ if and only if the set of tiles $f(e)$ can tile the plane.

From this we conclude that the set of finite sets of shapes which tile the plane is not computable, since otherwise - pulling back along $f$ - we could compute the halting problem.

At this point, maybe (I haven't read the proof in detail in a long time) it turns out that every set of tiles of the form $f(e)$ which does tile the plane, does so in a "hierarchical" fashion (whatever that means). This might be the case; however, it would be wrong to say that the proof "only works for hierarchical tilings," since the tilings aren't the 'inputs' to the theorem. Additionally, I'd be very surprised if this were true: I have a vague picture in my head of what "hierarchical" ought to mean to me, and my recollection is that the tilings constructed in the proof of undecidability of the tiling problem appear to be not hierarchical.

It might be the case that all the images of all such reductions $f$ all have to mostly consist of hierarchically tilable sets of tiles; for example, it is conceivable that

There is no computable function $f$ from $\mathbb{N}$ to $\{$finite sets of tiles$\}$, such that (i) $f(e)$ can tile the plane if and only if $\Phi_e(e)\uparrow$, and (ii) each set of tiles $f(e)$ (for $\Phi_e(e)\uparrow$) can not tile the plane hierarchically.

Depending on the definition of "hierarchical," I'd be surprised by that result, but in principle it could be true. However, if true it would require considerable work to prove, probably more than proving the original result.

None of the above, by the way, relies on aperiodicity. Where aperiodicity arises is in the fact that, if every set of tiles which could tile the plane could do so periodically, then the tiling problem would be computable (see the bottom of the first page of the article), so we must be using mostly sets of tiles which do not tile the plane periodically. That is, a lemma standing 'morally' (at least I think so) at odds to the undecidability of the tiling problem is:

There is no computable function $f$ from $\mathbb{N}$ to $\{$finite sets of tiles$\}$ such that $(i)$ $f(e)$ can tile the plane if and only if $\Phi_e(e)\uparrow$, and $(ii)$ if $\Phi_e(e)\uparrow$ then $f(e)$ can tile the plane periodically.

So aperiodicity is really an after-the-fact thing: because the tiling problem is unsolvable, it therefore follows that there are finite sets of tiles which can tile the plane, but can not do so periodically. (This is the first full sentence on page 178 of Robinson's article.)


I'm a little unclear, though, exactly what your question is, so I might not have addressed it well; is this what you were looking for?

share|improve this answer
    
By the way, I think this question is borderline for MO; certainly it could be clearer. On the other hand, issues about reductions in logic are notoriously subtle when encountered for the first time, which is why I've tried to answer it. –  Noah S Jan 8 at 1:48
    
I just read the paper, so it's fresh for me: the tile sets used in the proof are "hierarchical" in the sense that they're built on top of a particular tile set which tiles the plane (only) hierarchically. The fact that none of those tile sets can tile the plane periodically follows easily from that structure. –  Anton Malyshev Jan 8 at 2:26
    
I guess I'm still confused: what does "hierarchical" mean? –  Noah S Jan 8 at 2:26
    
As far as I can tell, when Scott C says a tile set is hierarchical, he means that it some specific proof technique can be sued to show that it doesn't tile the plane periodically. I think the important thing is that the hierarchical tile sets are recursively enumerable, can't tile the plane periodically, and include the tile sets used in the proof of undecidability. There's a suitable definition for "hierarchical" that makes that true. –  Anton Malyshev Jan 8 at 2:41
    
Well, that can't be it - if they were recursively enumerable, that would solve the tiling problem. Maybe what is meant is "the intersection of the set of tiling tile sets with an r.e. set?" –  Noah S Jan 8 at 2:45

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.