# New Pentagons

August 11, 2015 11:50 AM Subscribe

Mathematicians discover a new type of pentagon that can cover the plane leaving no gaps and with no overlaps. It becomes only the 15th type of pentagon known that can do this, and the first discovered in 30 years.

Previously on Mefi: No Pentagons (main link isn't working, but check out The Trouble with Five and this article on Marjorie Rice, an amateur mathematician who discovered four of the 15 known pentagonal tilings, linked in the comments.)

Bonus for '80s math-nerd kids: "Tessellations" song from Square One Television. Ooh-bop-bop-ooh!

Previously on Mefi: No Pentagons (main link isn't working, but check out The Trouble with Five and this article on Marjorie Rice, an amateur mathematician who discovered four of the 15 known pentagonal tilings, linked in the comments.)

Bonus for '80s math-nerd kids: "Tessellations" song from Square One Television. Ooh-bop-bop-ooh!

This sort of thing brings back fond memories of reading Martin Gardner's

posted by Major Clanger at 11:57 AM on August 11, 2015 [4 favorites]

*Mathematical Games*articles that my dad photocopied from*Scientific American*in his office library back in the 1970s.posted by Major Clanger at 11:57 AM on August 11, 2015 [4 favorites]

Can we make dice with this?

posted by Faint of Butt at 12:01 PM on August 11, 2015 [1 favorite]

posted by Faint of Butt at 12:01 PM on August 11, 2015 [1 favorite]

*Every triangle can tile the plane.*

**Every four-sided shape**can also tile the plane.Is this true (the bolded bit)? It feels to me like a concave quadrilateral wouldn't necessarily be able to do this. Although my intuition is probably wrong.

posted by dng at 12:01 PM on August 11, 2015 [1 favorite]

For a second there, I thought the mathematicians had finally proved the hippies were right and "Pentagons can levitate, man!"

posted by jonp72 at 12:07 PM on August 11, 2015 [2 favorites]

posted by jonp72 at 12:07 PM on August 11, 2015 [2 favorites]

It's impossible to tile the plane with regular pentagons, but trying to plug in the gaps with extra shapes like diamonds and stars yields some fascinating patterns, which show up in Islamic art.

posted by Rangi at 12:07 PM on August 11, 2015 [14 favorites]

posted by Rangi at 12:07 PM on August 11, 2015 [14 favorites]

I'm not a mathematician, but casual inspection of the example image shows this is only true if one allows that reflections of a shape should be considered to be identical with that shape? I don't know if this is the custom generally.

posted by JHarris at 12:11 PM on August 11, 2015 [7 favorites]

posted by JHarris at 12:11 PM on August 11, 2015 [7 favorites]

*Can we make dice with this?*

Dunno, but tabletop RPGS should totally set aside their usual square grid or hex grid combat maps for this during combats on the astral plane.

posted by ricochet biscuit at 12:15 PM on August 11, 2015 [21 favorites]

Great, but there are lots of polygons who can tile the plane. What I need to find is a polygon who can tile my bathroom, at a reasonable price. Find THAT polygon for me, eggheads. Also we need a polygon to do a loft conversion. Some people say I should contact a builder, but I say: NO. I want a polygon.

posted by the quidnunc kid at 12:17 PM on August 11, 2015 [47 favorites]

posted by the quidnunc kid at 12:17 PM on August 11, 2015 [47 favorites]

I'm going to be really disappointed if the floors in the Pentagon are not, in fact, tiled with pentagons.

posted by xedrik at 12:19 PM on August 11, 2015 [3 favorites]

posted by xedrik at 12:19 PM on August 11, 2015 [3 favorites]

*"Attack on the pentagon results in discovery of new mathematical tile "*

Interesting choice of words.

Interesting choice of words.

Problems worthy of attack prove their worth by fighting back.

posted by Pogo_Fuzzybutt at 12:22 PM on August 11, 2015 [2 favorites]

Neat.

It just occurred to me: do mathematicians study

Any shape which tiles the plane could be extruded along the third dimension to give it thickness, and the resulting shape would also tessellate three-dimensionally. A block—an extruded rectangle—is the most trivial example of this. (And various simple variations on a block, such as a block sliced in two equal halves along an angle.)

A four-sided pyramid would also work, wouldn't it?

posted by escape from the potato planet at 12:28 PM on August 11, 2015 [1 favorite]

It just occurred to me: do mathematicians study

*three*-dimensional tessellations? I mean, I'm sure they do. I've just never seen it discussed.Any shape which tiles the plane could be extruded along the third dimension to give it thickness, and the resulting shape would also tessellate three-dimensionally. A block—an extruded rectangle—is the most trivial example of this. (And various simple variations on a block, such as a block sliced in two equal halves along an angle.)

A four-sided pyramid would also work, wouldn't it?

posted by escape from the potato planet at 12:28 PM on August 11, 2015 [1 favorite]

*I'm not a mathematician, but casual inspection of the example image shows this is only true if one allows that reflections of a shape should be considered to be identical with that shape? I don't know if this is the custom generally.*

My understanding is that the requirement is congruence, which allows for reflections.

posted by mr_roboto at 12:35 PM on August 11, 2015 [2 favorites]

Yay!

I don't think the three- or higher order dimension study is called tesselation - tesselae are tiles, hence flat.

posted by Segundus at 12:38 PM on August 11, 2015 [1 favorite]

I don't think the three- or higher order dimension study is called tesselation - tesselae are tiles, hence flat.

posted by Segundus at 12:38 PM on August 11, 2015 [1 favorite]

The pentagons in the third example in the article (shown in red) kinda remind me of Vincent Adultman—the character from Bojack Horseman who is actually three kids stacked up in a trench coat. Like those pentagons got together and decided to dress up as a six-sided polygon so they could crash the hexagons' tile the plane party but they fall in love with a beautiful hexagon and hilarious geometric hi-jinks ensue.

posted by metaphorever at 12:41 PM on August 11, 2015 [4 favorites]

posted by metaphorever at 12:41 PM on August 11, 2015 [4 favorites]

*It just occurred to me: do mathematicians study three-dimensional tessellations?*

Yes, they do. It's harder to find regular solids that fill space, though. The triangle, square, and hexagon can all tile the plane, but only the cube (out of the five Platonic solids) can fill space. I think the rhombic dodecahedron is the only other polyhedron with all congruent faces (twelve rhombi) that fills space.

posted by Rangi at 12:42 PM on August 11, 2015 [1 favorite]

Maybe my brain doesn't process this right. If all triangles can tile, and all squares can tile, and a pentagon is just a shape with 5 straight sides, then could you not just tile a pentagon that has a square base and a triangle top? Like a house? In the examples they have a kind of house shape but with different angles, does that example encompass ALL of those types of shapes or just the one with those specific angles?

posted by Hazelsmrf at 12:49 PM on August 11, 2015 [1 favorite]

posted by Hazelsmrf at 12:49 PM on August 11, 2015 [1 favorite]

I'm not a math guy at all, but I was drawn to this thread by the use of "cover the plane" when—from what little I know of the subject—I was expecting "cover

posted by Ian A.T. at 12:50 PM on August 11, 2015

*a*plane." Is this idiomatic, or is it a specific piece of mathematics lingo I don't understand?posted by Ian A.T. at 12:50 PM on August 11, 2015

*Maybe my brain doesn't process this right. If all triangles can tile, and all squares can tile, and a pentagon is just a shape with 5 straight sides, then could you not just tile a pentagon that has a square base and a triangle top?*

You totally could. You note the example with a slanty house; the article is talking about classes of pentagons, of which e.g. "house-shaped" (in more formal terms) is presumably one, incorporating straight houses and slanty houses alike.

*Is this idiomatic, or is it a specific piece of mathematics lingo I don't understand?*

Common idiom, yeah. Plane geometrists will not shut

*up*about Tiling The proverbial Plane, it's like a sickness.

posted by cortex at 12:53 PM on August 11, 2015 [8 favorites]

Awesome The Laundry RPG material

posted by Bwithh at 12:54 PM on August 11, 2015 [2 favorites]

posted by Bwithh at 12:54 PM on August 11, 2015 [2 favorites]

For the reasons behind plane geometrists' insistence upon the use of the definite article, please see the sterling work by Villechaize et al.

> ...

Yeah, Eric Broug's social media stream went nuts about this this morning.

posted by scruss at 1:11 PM on August 11, 2015 [4 favorites]

> ...

*some fascinating patterns, which show up in Islamic art.*Yeah, Eric Broug's social media stream went nuts about this this morning.

posted by scruss at 1:11 PM on August 11, 2015 [4 favorites]

*Joy as mathematicians discover a new type of pentagon*

I'm picturing a bunch of mathematicians passed out after a huge rager with hookers and blow underneath a framed picture of the joyous new pentagon.

Man, I shoulda been a mathematician.

posted by Justinian at 1:15 PM on August 11, 2015 [5 favorites]

More seriously, this seems like the type of problem that should be susceptible to brute-force attack with computers?

posted by Justinian at 1:16 PM on August 11, 2015

posted by Justinian at 1:16 PM on August 11, 2015

*"only the 15th type of pentagon known that can do this"*

That doesn't sound very impressive to me, but what do I know.

posted by w0mbat at 1:16 PM on August 11, 2015

That picture of all the different pentagonal tilings... I've never wanted a house with 15 bathrooms before.

posted by Homeboy Trouble at 1:23 PM on August 11, 2015 [11 favorites]

posted by Homeboy Trouble at 1:23 PM on August 11, 2015 [11 favorites]

*More seriously, this seems like the type of problem that should be susceptible to brute-force attack with computers?*

That's how they found this one.

posted by mr_roboto at 1:28 PM on August 11, 2015 [3 favorites]

We here at MeFi are still searching for the fifteenth known member who reads the articles before commenting.

posted by tonycpsu at 1:30 PM on August 11, 2015 [33 favorites]

posted by tonycpsu at 1:30 PM on August 11, 2015 [33 favorites]

*That's how they found this one.*

I'm just surprised that every possible pentagon hasn't been tried. Maybe I'm grossly underestimating how many possibilities there are.

posted by Justinian at 1:37 PM on August 11, 2015

*I was expecting "cover a plane." Is this idiomatic*

When you consider planes embedded in 3D, you can distinguish between two planes based on their angles of orientation. But in 2D, there is only one plane, and it's

*the*plane.

posted by grog at 1:38 PM on August 11, 2015 [2 favorites]

Having thought about it more, I realize that what I was thinking about is really just searching "a large but finite" set of pentagons which is what they did here. No matter how large the set of pentagons you search I guess you can't be absolutely positive that nudging the angles fractionally towards a limit won't yield a tiling pentagon.

posted by Justinian at 1:41 PM on August 11, 2015

posted by Justinian at 1:41 PM on August 11, 2015

*a new type of pentagon that can cover the plane leaving no gaps and with no overlaps*

This sounds like something a 9/11 conspiracy Twitter bot would come up with.

posted by prize bull octorok at 1:44 PM on August 11, 2015 [7 favorites]

All I know is that we should get these motherfucking tiles off this motherfucking pla- oh wait it's not 2006 anymore. Shit. Uh ... "All your plane belong to ti- no, wait. Sorry. Umm ... I'm still "cool" and "with it", right guys? You'd tell me if I wasn't. Right? Guys?

posted by the quidnunc kid at 1:53 PM on August 11, 2015 [5 favorites]

posted by the quidnunc kid at 1:53 PM on August 11, 2015 [5 favorites]

I know that there are people who study tiling of fractals. (as a non-mathematics person this kind of makes my head go squishy).

Once we tried doing a basic experiment in tiling 3-space by taking water balloons, filling a chest freezer, turning the freezer on and then seeing what shapes they made. It took longer to freeze than we'd anticipated and it ended up being a really cold water balloon fight on a hot summer day.

This is what happens when you have a mathematician as a parent.

Space filling polyhedra.

posted by sciencegeek at 2:02 PM on August 11, 2015 [5 favorites]

Once we tried doing a basic experiment in tiling 3-space by taking water balloons, filling a chest freezer, turning the freezer on and then seeing what shapes they made. It took longer to freeze than we'd anticipated and it ended up being a really cold water balloon fight on a hot summer day.

This is what happens when you have a mathematician as a parent.

Space filling polyhedra.

posted by sciencegeek at 2:02 PM on August 11, 2015 [5 favorites]

another fun place to look at 3D tiling is in soap bubbles - blow a pile of similar sized bubbles and look at the shapes they form.

posted by sciencegeek at 2:03 PM on August 11, 2015 [1 favorite]

posted by sciencegeek at 2:03 PM on August 11, 2015 [1 favorite]

Determining whether sets of tiles tile the plane is of course a classic non-computable problem, because there are sets that tile the plane only aperiodically: a result proved by Robert Berger by analogy with Turing and in contradiction to Hao Wang. Berger's original set was huge, but Roger Penrose has produced very simple sets that tile only aperiodically.

posted by Segundus at 2:06 PM on August 11, 2015 [5 favorites]

posted by Segundus at 2:06 PM on August 11, 2015 [5 favorites]

*no convex heptagon, octagon, or anything else-gon tiles the plane*

This does not include dra-gons, which do pretty much whatever they want

posted by oulipian at 2:07 PM on August 11, 2015 [3 favorites]

Type 10 is kind of fucking with the pattern-recognition parts of my brain.

posted by truex at 2:34 PM on August 11, 2015 [5 favorites]

posted by truex at 2:34 PM on August 11, 2015 [5 favorites]

Alex Bellos does a fantastic job of writing breezily about math without breezily getting the details wrong. For instance, he gives the exact value of the length of

One of Marjorie Rice's pentagons was used to make the board for the board for Pex, a variant of Hex.

posted by Wolfdog at 3:41 PM on August 11, 2015 [3 favorites]

*c*, where this kind of writing would often just give it to a decimal place or two, without comment. So I can see quickly that the minimal polynomial for it is 16x^{4}-16x^{2}+1, which is nice and tidy.One of Marjorie Rice's pentagons was used to make the board for the board for Pex, a variant of Hex.

posted by Wolfdog at 3:41 PM on August 11, 2015 [3 favorites]

♫ SQUARE ONE! *doot doot-doot dooooo-doot dooo-doot doooo* ♫

posted by teponaztli at 3:55 PM on August 11, 2015

posted by teponaztli at 3:55 PM on August 11, 2015

I don't like the "Attack on the pentagon" click-bait title. Here's another article with the same basic information, including this handy illustration of all the tiling pentagon shapes so far.

posted by King Sky Prawn at 4:16 PM on August 11, 2015

posted by King Sky Prawn at 4:16 PM on August 11, 2015

*Determining whether sets of tiles tile the plane is of course a classic non-computable problem, because there are sets that tile the plane only aperiodically: a result proved by Robert Berger by analogy with Turing and in contradiction to Hao Wang. Berger's original set was huge, but Roger Penrose has produced very simple sets that tile only aperiodically.*

There is an even deeper result, quite counter-intuitive: William Hanf and Dale Myers proved that there are tile sets that can tile the plane, but no such tiling can be algorithmically generated. This is in contrast to Wang's and Berger's and Penrose's tilings, for which you can write a computer program that draws them, for as large of a subpattern as you want.

One of the most remarkable and under-appreciated results I know. I wish I could point you to an understandable exposition of these results, which really aren't harder to understand than the undecidability of the halting problem, once you wrap your head around them. But as far as I know, no one has written such an exposition.

posted by brambleboy at 7:18 PM on August 11, 2015 [9 favorites]

*fills space*

This seems less exciting than "Tile The Plane". I'm going to go for "Brick The Volume" for 3 dimensional space, or possibly "Gleam The Cube". "Hack The Gibson" can be for anything with 3+ dimensions, since I am incapable of understanding that in any sensical manner.

posted by Jon Mitchell at 8:34 PM on August 11, 2015 [7 favorites]

brambleboy: "

I'd love that too, because that sounds mind-bogglingly counterintuitive. How does that even work? Can you give some sort of idea at all of how that can be true?

posted by Joakim Ziegler at 1:41 AM on August 12, 2015

*One of the most remarkable and under-appreciated results I know. I wish I could point you to an understandable exposition of these results, which really aren't harder to understand than the undecidability of the halting problem, once you wrap your head around them. But as far as I know, no one has written such an exposition.*"I'd love that too, because that sounds mind-bogglingly counterintuitive. How does that even work? Can you give some sort of idea at all of how that can be true?

posted by Joakim Ziegler at 1:41 AM on August 12, 2015

Can it be extended to N dimensions? I remember back when I just started at computing, working with a guy who was excited that he could make models of hypercubes and make N-dimensional data structures in APL (A Programming Language). At that moment, considering higher-dimensional geometries was a hot topic.

Maybe there is a series of structures (an "N-cube") that fills in every dimensionality?

posted by newdaddy at 3:59 AM on August 12, 2015

Maybe there is a series of structures (an "N-cube") that fills in every dimensionality?

posted by newdaddy at 3:59 AM on August 12, 2015

Another way to create this interesting irregular pentagon: call length "b" 1 rather than 1/2. Extend a line from "B" at 60 degrees from "b" down to "a", creating an equilateral triangle. Let's call the intersection point of that line with "a" "F", so B-A-F is our first equilateral triangle. Make an inverted equilateral triangle to the left of the first one which shares side B-F, then make a third equilateral triangle with the same "upright" orientation as B-A-F, which needs a new vertex at "G", and which shares side F-G with the middle inverted triangle.

Now from the third leftmost triangle construct a square with side E-G as one of its sides. From the square's corner "C" extend a line to vertex "B", completing the pentagon. Interesting way to connect a square with an equilateral triangle!

I fucking burned my oatmeal while trying to explain this, and now I have to go to work.

posted by Agave at 4:20 AM on August 12, 2015 [4 favorites]

Now from the third leftmost triangle construct a square with side E-G as one of its sides. From the square's corner "C" extend a line to vertex "B", completing the pentagon. Interesting way to connect a square with an equilateral triangle!

I fucking burned my oatmeal while trying to explain this, and now I have to go to work.

posted by Agave at 4:20 AM on August 12, 2015 [4 favorites]

Alex Bellos's first book is called "Here's looking at Euclid" in the US, which is some next level punning

posted by fatfrank at 5:04 AM on August 12, 2015 [3 favorites]

posted by fatfrank at 5:04 AM on August 12, 2015 [3 favorites]

Well, since you asked. Here is a brief, words-only summary of the Hanf and Myers result. Sorry about the lack of diagrams. First, two bits of background.

(1) The standard tiling problem asks "is it possible to tile the infinite plane, with no gaps or overlaps, using tiles only from the given finite set?" Note that not all the tiles have to be used. For example, the set "equilateral triangle and equilateral pentagon" does tile the plane -- just don't use the pentagon. The related "origin-constrained" tiling problem asks whether you can tile the plane using a particular tile placed at the origin. In the above example, if you restrict to having a single pentagon at the origin, sorry, game over. In an obscure technical report, Hao Wang realized that the origin-constrained tiling problem is undecidable; Robert Berger's later contribution was to generalize this result to the unconstrained case.

(2) Wang's result is the most interesting part, to me. Given an arbitrary Turing machine and a chosen input, you can create a set of essentially square tiles that fit together to reproduce the space-time history of the Turing machine execution -- given that the "input tile" is placed at the origin. You can think of the square tiles as having labels (or colors, or notches and protrusions) on each side, such that they fit next to each other only if the labels match. There is a unique tile that fits next to the input tile, and a unique one that fits next to that, and so forth, making a horizontal line that encodes the full input to the Turing machine and the input string in the labels on the top of each tile. Binding to the last unique tile is a tile that binds to itself repeatedly until infinity, encoding the blank symbol on its top. And similarly to go to infinity on the other side of the input. The clever part comes in selecting tiles that fit in the next layer, such that each layer corresponds to one step of the Turing machine. (Here is a nice explanation with illustrations; it's straightforward, but there are many details.)

So, with that background, let's assume that getting tiles to simulate a Turing machine isn't hard -- and if we're even more clever, we can play games to make them use no more space than is needed (e.g. rather than an infinite blank space on both sides, just use a slowly growing-as-necessary space, so we can use the rest of the tiling to do other things. Hanf showed that origin-constrained tilings can be non-recursive (i.e. can't be generated by an algorithm) while Myers showed that the result holds still in the unconstrained case. The following is my best recollection of an unpublished construction due to Matt Cook, which is a concrete example of the kind of thing that Hanf more abstractly showed must exist.

We design a tile set such that the horizontal line to the right of the origin must consist of black or white tiles such that the nth tile is white if the nth Turing machine (list Turing machines in some conventional order) halts after an odd number of steps, is black if the nth Turing machine halts after an even number of steps, and is either black or white if the nth Turing machine doesn't ever halt. In fact, our tile set will allow an uncountable number of valid tilings, but they will all have the correct color for every Turing machine that actually halts, and "random" colors for every Turing machine that doesn't halt (on an empty input tape, in all cases). It would be nicer if the B/W tiles encoded the answers to the Halting Problem for the nth Turing machine, but that isn't possible. (Exercise to the reader: use Konig's lemma to show that if a tile set produces a unique origin-constrained tiling, then it can be algorithmically generated. In fact, non-recursive tile sets must have uncountably many tilings.)

The point is that no matter what choices are made for the non-halting Turing machines, systematic or random or whatever, the B/W pattern is non-recursive. (Exercise to the reader: use a diagonal argument to show this.) Intuitively, an algorithm that tries to output the right value for all halting Turing machines, but make an arbitrary choice for non-halting Turing machines, runs into the danger of not being sure when to give up and make an arbitrary choice and when to keep trying to figure out the right answer.

So how do we design a tile set that enforces this pattern of B/W tiles? Basically, we use the space above the horizontal B/W line to run all possible Turing machines, going vertically. Think of a bunch of bamboo stalks. Whenever one halts, it sends back a runner to signal either Even or Odd. For Turing machines that don't halt, there will be an arbitrarily colored runner heading up to infinity, and since the Turing machine never halts, it will never connect and note an inconsistency. Thus the tiling will be valid. The (actually quite tricky) trick in all this is making sure that there's enough space for all the Turing machines to run. But that's the picture.

The intuition is that the existence of a tiling simply asks for consistency, so it's easy to "make random guesses" and the inconsistent ones get filtered out -- this is something that algorithms can't do.

Not sure that helped. OK, back to my day job, feeling a little silly about writing so much technical-ish blah. But it really is one of my favorite results.

posted by brambleboy at 3:11 PM on August 12, 2015 [8 favorites]

(1) The standard tiling problem asks "is it possible to tile the infinite plane, with no gaps or overlaps, using tiles only from the given finite set?" Note that not all the tiles have to be used. For example, the set "equilateral triangle and equilateral pentagon" does tile the plane -- just don't use the pentagon. The related "origin-constrained" tiling problem asks whether you can tile the plane using a particular tile placed at the origin. In the above example, if you restrict to having a single pentagon at the origin, sorry, game over. In an obscure technical report, Hao Wang realized that the origin-constrained tiling problem is undecidable; Robert Berger's later contribution was to generalize this result to the unconstrained case.

(2) Wang's result is the most interesting part, to me. Given an arbitrary Turing machine and a chosen input, you can create a set of essentially square tiles that fit together to reproduce the space-time history of the Turing machine execution -- given that the "input tile" is placed at the origin. You can think of the square tiles as having labels (or colors, or notches and protrusions) on each side, such that they fit next to each other only if the labels match. There is a unique tile that fits next to the input tile, and a unique one that fits next to that, and so forth, making a horizontal line that encodes the full input to the Turing machine and the input string in the labels on the top of each tile. Binding to the last unique tile is a tile that binds to itself repeatedly until infinity, encoding the blank symbol on its top. And similarly to go to infinity on the other side of the input. The clever part comes in selecting tiles that fit in the next layer, such that each layer corresponds to one step of the Turing machine. (Here is a nice explanation with illustrations; it's straightforward, but there are many details.)

So, with that background, let's assume that getting tiles to simulate a Turing machine isn't hard -- and if we're even more clever, we can play games to make them use no more space than is needed (e.g. rather than an infinite blank space on both sides, just use a slowly growing-as-necessary space, so we can use the rest of the tiling to do other things. Hanf showed that origin-constrained tilings can be non-recursive (i.e. can't be generated by an algorithm) while Myers showed that the result holds still in the unconstrained case. The following is my best recollection of an unpublished construction due to Matt Cook, which is a concrete example of the kind of thing that Hanf more abstractly showed must exist.

We design a tile set such that the horizontal line to the right of the origin must consist of black or white tiles such that the nth tile is white if the nth Turing machine (list Turing machines in some conventional order) halts after an odd number of steps, is black if the nth Turing machine halts after an even number of steps, and is either black or white if the nth Turing machine doesn't ever halt. In fact, our tile set will allow an uncountable number of valid tilings, but they will all have the correct color for every Turing machine that actually halts, and "random" colors for every Turing machine that doesn't halt (on an empty input tape, in all cases). It would be nicer if the B/W tiles encoded the answers to the Halting Problem for the nth Turing machine, but that isn't possible. (Exercise to the reader: use Konig's lemma to show that if a tile set produces a unique origin-constrained tiling, then it can be algorithmically generated. In fact, non-recursive tile sets must have uncountably many tilings.)

The point is that no matter what choices are made for the non-halting Turing machines, systematic or random or whatever, the B/W pattern is non-recursive. (Exercise to the reader: use a diagonal argument to show this.) Intuitively, an algorithm that tries to output the right value for all halting Turing machines, but make an arbitrary choice for non-halting Turing machines, runs into the danger of not being sure when to give up and make an arbitrary choice and when to keep trying to figure out the right answer.

So how do we design a tile set that enforces this pattern of B/W tiles? Basically, we use the space above the horizontal B/W line to run all possible Turing machines, going vertically. Think of a bunch of bamboo stalks. Whenever one halts, it sends back a runner to signal either Even or Odd. For Turing machines that don't halt, there will be an arbitrarily colored runner heading up to infinity, and since the Turing machine never halts, it will never connect and note an inconsistency. Thus the tiling will be valid. The (actually quite tricky) trick in all this is making sure that there's enough space for all the Turing machines to run. But that's the picture.

The intuition is that the existence of a tiling simply asks for consistency, so it's easy to "make random guesses" and the inconsistent ones get filtered out -- this is something that algorithms can't do.

Not sure that helped. OK, back to my day job, feeling a little silly about writing so much technical-ish blah. But it really is one of my favorite results.

posted by brambleboy at 3:11 PM on August 12, 2015 [8 favorites]

brambleboy, please don't feel silly. you have genuinely blown my mind and made my personal universe a little bit richer. thank you.

posted by TheNewWazoo at 9:11 PM on August 12, 2015 [1 favorite]

posted by TheNewWazoo at 9:11 PM on August 12, 2015 [1 favorite]

Okay, so this did get my attention in the various pentagon patterns and I'm trying to learn more. Where should I start?

I've found that Wolfram Alpha has the previous 14 types, and gives you adjustable parameters like an angle or side when the type is a range of possibilities. But it's not immediately clear to me which side or angle I'm adjusting without making a lot of guesses. And it doesn't give me the dimensions of the rest of the sides either. (It's now only the very latest one that I've seen the dimensions and angles of all the sides, in the Guardian article.)

It does give some stuff I think help me a lot, like the "Primitive Unit" I think is a repeating pattern of pentagons which itself can be tiled as a non-pentagon. The translation vectors define how far that primitive unit is moved to tile. (But I would need to know the dimensions of the pentagons for to fully use that)

I've read some Wikipedia stuff on the symmetry like what is P2 and 2222 but I'm not entirely wrapping my head around that.

This page has formulas for all of them but I think assumes I know more conventions than I do. Is it always the rule like the Guardian article, that b is between B and A, and c is between C and B, and so on?

posted by RobotHero at 8:57 PM on August 17, 2015

I've found that Wolfram Alpha has the previous 14 types, and gives you adjustable parameters like an angle or side when the type is a range of possibilities. But it's not immediately clear to me which side or angle I'm adjusting without making a lot of guesses. And it doesn't give me the dimensions of the rest of the sides either. (It's now only the very latest one that I've seen the dimensions and angles of all the sides, in the Guardian article.)

It does give some stuff I think help me a lot, like the "Primitive Unit" I think is a repeating pattern of pentagons which itself can be tiled as a non-pentagon. The translation vectors define how far that primitive unit is moved to tile. (But I would need to know the dimensions of the pentagons for to fully use that)

I've read some Wikipedia stuff on the symmetry like what is P2 and 2222 but I'm not entirely wrapping my head around that.

This page has formulas for all of them but I think assumes I know more conventions than I do. Is it always the rule like the Guardian article, that b is between B and A, and c is between C and B, and so on?

posted by RobotHero at 8:57 PM on August 17, 2015

« Older Canids will be canids | The Philosopher of Surveillance Newer »

This thread has been archived and is closed to new comments

Attack on the pentagonresults in discovery of new mathematical tile "Interesting choice of words. But on the topic itself, interesting stuff, thanks for sharing.

posted by filthy light thief at 11:55 AM on August 11, 2015 [5 favorites]