Pentagon Tiling Proof Solves Century-Old Math Problem

Re:Pentagon Tiling Proof Solves Century-Old Math Problem by DonbunEf7 on Tuesday July 11, 2017 @04:24PM (#14747723)

Wang tiles, mentioned only at the end of the article, encode Turing-equivalent computation in their simple color-matching rule. It is unknown exactly how useful Wang tiles are to theory of computation, other than as a wonderful demonstration of how easily Turing-complete systems arise naturally.

I suspect that tiling may have applications in resource management, particularly when allocating resources like memory which have an underlying topological structure.

Edit: https://arxiv.org/pdf/1506.06492.pdf is worth considering, but I don't yet know what its relevance is.

[ Parent | on HN ]

Re:Pentagon Tiling Proof Solves Century-Old Math Problem by doctoboggan on Tuesday July 11, 2017 @11:19PM (#14749928)

Greg Egan explores the concept of Wang tiles as a naturally occurring computer in his excellent novel "Diaspora":

http://www.gregegan.net/DIASPORA/DIASPORA.html

It gets a bit dense at times, but I would highly recommend it, especially if you are interested in turing complete systems.

[ Parent | on HN ]

Re:Pentagon Tiling Proof Solves Century-Old Math Problem by chriswarbo on Wednesday July 12, 2017 @06:02AM (#14751301)

Wang tiles made from DNA (using bases to encode the "colours", so matching up base pairs enforces the rules) have been used to perform computation.

AFAIK it's not yet a practical tool, but the choice of Wang tiles was practical for the experimenters since they're known to be Turing complete, and hence make for a more compelling demonstration.

http://www.dna.caltech.edu/Papers/FOE_2003_final.pdf

[ Parent | on HN ]