Tiling with Three Polygons Is Undecidable
136 points by denvaar 7 days ago | 27 comments
  • xianshou 4 days ago |
    First you ask how the hell someone could come up with this construction.

    Then you realize it was this guy: https://en.wikipedia.org/wiki/Erik_Demaine

    • heavensteeth 4 days ago |
      >former child prodigy

      I understand the idea behind that phrasing but I'm not sure I agree with it. Are you no longer a child prodigy once you turn 18? I don't think I'd ever say "former intelligent child".. Would I?

      • chuckadams 4 days ago |
        It's a little weird to call a 43-year-old a "child prodigy", yes. The phrase is left-associative.
      • infogulch 4 days ago |
        Well he was a child prodigy, but he is no longer a child. A suitable replacement would need to reword the sentence to be about the same length and include that detail without the odd sounding wording.
        • chongli 4 days ago |
          How about just prodigy?
          • irjustin 4 days ago |
            For this context, prodigy only applies to children. I'd never call an adult a prodigy except for they were a "former child prodigy".

            Somewhere along the line you convert from child prodigy to genius assuming you maintained your ability above the rest of the pack.

        • infogulch 3 days ago |
          Maybe "was considered a prodigy as a child" has the implications more clearly aligned, though it is a bit longer.
      • noman-land 4 days ago |
        This is why I refer to my wife as my ex-girlfriend.
        • Etheryte 4 days ago |
          Oh this is devious, I am definitely going to steal this and get smacked for it.
        • dclowd9901 4 days ago |
          This is really funny and I’d steal it if I thought I could get away with it.
      • kortilla 4 days ago |
        Yes, child prodigy is entirely about being a child.
      • furyofantares 4 days ago |
        How do you feel about "former child actor"?
      • Mountain_Skies 4 days ago |
        Every year we hear about some kid who is "smarter than Einstein and Hawking" but for the most part, we never hear about them again. Child prodigies that turn into extraordinary adults seem to be rare. If you were to ask me to name some, the only one I'd be able to name off hand would be Stephen Wolfram. That here is another one is of interest even if it is of little consequence to his current accomplishments.
        • sfn42 4 days ago |
          I think the bar has been raised. As science has progressed and evolved, all the "low hanging fruit" has been picked.

          As an example, take Dijkstra's algorithm. It's far from the only thing that he is known for and I am by no means trying to diminish his accomplishments but how many people really tried to solve that problem before him?

          I might be subject to some kind of fallacy or bias but I feel like if I'd never heard of Dijkstra and was presented with the task to find the shortest path between two nodes in a graph I could have come up with that algorithm. Maybe not in the first day but eventually at least.

          It's that whole "standing on the shoulders of Giants" thing. The giants allow us to see further by learning from and building on their work, but they also picked a lot of the low hanging fruits in their career. Sure they left a lot of things undone but they probably picked out the juiciest lowest hanging fruits first and most of the ones left are either less juicy or higher up or both.

          As this effect continues we end up in a situation where simply getting to the point where one can begin to push the boundaries of a specific field takes decades of learning from these giants before us, and now we're millions of people all looking for those juicy low hanging fruits while there's hardly any fruit left on the tree at all.

          All that to say I think it's unfair to compare modern researchers to Einstein and similar giants. Making a revolutionary discovery like these men have done is possibly less a matter of raw intelligence and more a matter of circumstance. You need the right people in the right place with the right people around them and the funding for it and so on.

          • nuancebydefault 3 days ago |
            Maybe Archimedes was not so smart after all. Especially since he was forced to think.
            • sfn42 3 days ago |
              I'm not saying they're not smart, I'm saying it takes more than just a smart man. If Einstein was born in Africa to a family barely scraping by, and never got an education do you think he'd have come up with his theory of relativity? That's a rhetorical question, it's pretty much just a fact that he wouldn't. So you need the genius, you need the education and all the other social infrastructure, lots of circumstance.

              Also I'm saying that nobody can come up with the theory of relativity again. That big juicy fruit is picked. I'm not saying it was low hanging, but it also wasn't at the top of the tree. Maybe if someone else figured out relativity and Einstein was born 40 years ago he would just be another relatively unknown physicist today. Maybe he'd have figured out some other amazing revolutionary thing, who knows. He certainly wouldn't have been the one to figure out relativity if it had already been done.

      • iterance 4 days ago |
        "He was a prodigy. He still is, but he was one, too."

        Very challenging to word in a succinct manner.

      • locallost 4 days ago |
        Interesting take so upvoted, but calling him a child prodigy does not work as he's not a child.

        Maybe "a child prodigy in his youth" would be both precise and succinct enough, but at the same time language is for humans and I feel humans know what is meant by former child prodigy.

    • atq2119 4 days ago |
      And then you read the abstract and realize that this is an improvement of an earlier result using five polygons (which in turn built on a history of earlier results).

      So, still a great result, but not as out there as one may think.

      I think it's also worth pointing out that in theoretical CS and most of math, it is common to list authors alphabetically. I don't think we have a way of knowing the relative contribution of the two authors. Demaine is obviously accomplished, but I find the kind of hero worship found in this thread distasteful and the facts don't support it here. Give credit to Langerman; Demaine surely would!

    • fuzzythinker 4 days ago |
    • _Donny 4 days ago |
      Woah! It is the same guy that got me through my algorithms course at university with his youtube MIT OpenCourseWare videos!

      His lectures are absolute gold. He explains everything so clearly, simply, and efficiently.

      I started skipping lectures in favor of watching his videos, and it saved me countless of hours -- and I got a perfect mark :)

  • romwell 4 days ago |
    Erik Demaine always has some fun stuff for us.
  • YoumuChan 4 days ago |
    The author gave a talk on this at Tufts during the FWCG last week. Fascinating talk.

    One interesting question from audience was whether the ratio between the largest polygon piece and the smallest piece can be made bounded, as the current construction has unbounded ratio.

  • whatshisface 4 days ago |
    That's reminicient of the post correspondence problem. Is the PCP still undecidable for sets of three strings?
    • petters 4 days ago |
      I don't think that is known. But the limit is low, something like five
  • joebergeron 4 days ago |
    I read the title of this paper and thought to myself, “What are the chances this could be Erik Demaine?”. And sure enough!
  • bryan0 3 days ago |
    While not proven, is the intuition that this will also be undecideable for 1 and 2 polygon tilings?