[HN Gopher] Tiling with Three Polygons Is Undecidable
___________________________________________________________________
Tiling with Three Polygons Is Undecidable
Author : denvaar
Score : 130 points
Date : 2024-11-17 05:51 UTC (3 days ago)
(HTM) web link (arxiv.org)
(TXT) w3m dump (arxiv.org)
| xianshou wrote:
| 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 wrote:
| >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 wrote:
| It's a little weird to call a 43-year-old a "child prodigy",
| yes. The phrase is left-associative.
| infogulch wrote:
| 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 wrote:
| How about just prodigy?
| irjustin wrote:
| 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 wrote:
| Maybe "was considered a prodigy as a child" has the
| implications more clearly aligned, though it is a bit
| longer.
| noman-land wrote:
| This is why I refer to my wife as my ex-girlfriend.
| Etheryte wrote:
| Oh this is devious, I am definitely going to steal this and
| get smacked for it.
| dclowd9901 wrote:
| This is really funny and I'd steal it if I thought I could
| get away with it.
| kortilla wrote:
| Yes, child prodigy is entirely about being a child.
| furyofantares wrote:
| How do you feel about "former child actor"?
| Mountain_Skies wrote:
| 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 wrote:
| 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 wrote:
| Maybe Archimedes was not so smart after all. Especially
| since he was forced to think.
| iterance wrote:
| "He was a prodigy. He still is, but he was one, too."
|
| Very challenging to word in a succinct manner.
| locallost wrote:
| 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 wrote:
| 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 wrote:
| His page - https://erikdemaine.org/
| _Donny wrote:
| 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 wrote:
| Erik Demaine always has some fun stuff for us.
| YoumuChan wrote:
| 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 wrote:
| That's reminicient of the post correspondence problem. Is the PCP
| still undecidable for sets of three strings?
| petters wrote:
| I don't think that is known. But the limit is low, something
| like five
| joebergeron wrote:
| I read the title of this paper and thought to myself, "What are
| the chances this could be Erik Demaine?". And sure enough!
| bryan0 wrote:
| While not proven, is the intuition that this will also be
| undecideable for 1 and 2 polygon tilings?
___________________________________________________________________
(page generated 2024-11-20 23:01 UTC)