3 ms·
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
by DonbunEf7 9y ago
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 https://arxiv.org/pdf/1506.06492.pdf is worth considering, but I don't yet know what its relevance is.
- doctoboggan 9y agoGreg Egan explores the concept of Wang tiles as a naturally occurring computer in his excellent novel "Diaspora": http://www.gregegan.net/DIASPORA/DIASPORA.html 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.
- chriswarbo 9y agoWang 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 http://www.dna.caltech.edu/Papers/FOE_2003_final.pdf