3 ms·
I was recently watching some Computerphile videos and was surprised to learn that several geometric problems have fundamental applications outside the physical
by bmc7505 9y ago
I was recently watching some Computerphile videos and was surprised to learn that several geometric problems have fundamental applications outside the physical sciences, such as geometric sphere packing and error correcting codes. Does tiling research have any known applications in CS or information theory?
- DonbunEf7 9y agoWang 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
- SOLAR_FIELDS 9y agoWorking with geographic systems, using tiling is a way to perform spatial indexing. If there are novel approaches to nonstandard (rectangular) tiling that better group geographic data for analysis, this could potentially lead to faster geographic computations in an area that is well known for having quite expensive approaches.
- rurban 9y agoMaterial physics obviously. If can aperiodically pack molecules better than before you got a new super material. With an "Einstein" (single molecul) it would be easiest, of course. Penrose like tilers need two and they are not so easy to arrange.