Hacker News Reader

Comment by bmc7505 | Hacker News Reader

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?

View on HN

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.

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.

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

Working 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.

Material 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.

Reply on news.ycombinator.com