From: nurban@crib.corepower.com (Nathan Urban) Newsgroups: sci.math Subject: Re: What are Wang dominoes/tiles? Date: 3 Jan 1999 20:50:32 -0500 In article <76otsn$dc0$1@plug.news.pipex.net>, "Andy Lee" wrote: > I have just finished reading the sci-fi novel Diaspora by Greg Egan which > features many interesting concepts based on mathematics, particle physics, > cosmology, sociology and A.I. Great book. Lots of mind-bending ideas, as usual with Egan. > Of special interest was the description of Wang dominoes or tiles > (mathematician Hao Wang), an organisation of which produces a hypothetical > lattice-based biochemical computer. The only definition I've been able to find is "Wang tiles are unit square tiles with colored edges". I'm not sure how you construct a universal Turing machine from them. I suppose the tiles would form a Turing machine memory with the colors encoding construction rules. > Can anybody offer more information on Wang tiles (pointers to > web sites would be very useful) and easily accessable journal/paper > references. Try: ftp://ftp.cs.sc.edu/pub/culik/tiles.ps.gz http://www.ics.uci.edu/~eppstein/junkyard/tiling.html http://www.nr.infi.net/~drmatrix/progchal.htm http://www.amath.umanitoba.ca/PM/Wang.html http://www.sam.math.ethz.ch/~pkeller/EGAN/Egan-MathStories.html The last page cites _Tilings and Patterns_ by Branko Gruenbaum and G.C. Shephard with respect to their computational properties. Of course, the most direct way of finding out is to just ask Egan where he read about them. (I'm surprised he didn't have any references in the back of _Diaspora_; I have it loaned out so I can't check, but I presume you looked.) He reads this newsgroup every once in a while, so he might see your article, but if not, try punctuating "gregegan netspace zebra net au" to get his e-mail address. (He only advertises the spam-blocked address so I'm doing the same.) Incidentally, on his web page he has a whole section dedicated to the math/physics of _Diaspora_: http://www.netspace.net.au/~gregegan/DIASPORA/DIASPORA.html ============================================================================== From: chavey@beloit.edu (Darrah Chavey) Newsgroups: sci.math Subject: Re: What are Wang dominoes/tiles? Date: Mon, 04 Jan 1999 09:13:23 -0600 In article <76otsn$dc0$1@plug.news.pipex.net>, "Andy Lee" wrote: > Hello folks and Happy New Year!, > > I have just finished reading the sci-fi novel Diaspora by Greg Egan which > features many interesting concepts based on mathematics, particle physics, > cosmology, sociology and A.I. > Of special interest was the description of Wang dominoes or tiles > (mathematician Hao Wang), an organisation of which produces a hypothetical > lattice-based biochemical computer. > This novel has introduced many interesting concepts which piqued my > curiosity. > > Can anybody offer more information on Wang tiles (pointers to > web sites would be very useful) and easily accessable journal/paper > references. I strongly recommend Chapter 11 of B. Grunbaum & G.C. Shephard, "Tilings and Patterns" for details beyond what I will describe here. In 1961, H. Wang conjectured that if you were given a finite set of tiles, that there would be an algorithm to decide if that set of tiles could be used to tile the plane. He also showed that this would be true if every set of tiles which could tile the plane could be used to tile the plane periodically. For references see: Bell System Tech. Journal 40(1961), pp. 1-42; or more easily: "Games, logic and computers" in Scientific American, Nov. 1965, pp. 98-106. Wang was thus the first person to ask about the existence of non-periodic tiles, most famously known now through the Penrose tilings and other tilings of that form. However, in 1961 (and even in '65 when the Sci. Am. article was published) no such tilings were known. In 1966, R. Berger found the first example of a set of non-periodic tiles, which he called "Wang tiles". (Ref: "The undecidability of the domino problem, Memoirs Amer. Math. Soc. 66(1966).) Since then, non-periodic tiles constructed using the style of Berger have been called "Wang tiles". (I hope you see the irony here.) To quote from Grunbaum & Shephard: "Wang tiles are square tiles with colored edges which must be placed edge-to-edge; colors on contiguous edges must match and only translations (not rotations or reflections) of the prototiles are allowed.... Their theoretical importance stems from the fact that it is possible to find sets of Wang tiles which mimic the behavior of any Turing machine [i.e., any computer], and so they are relevant to questions of mathematical logic .... In 1966 R. Berger discovered the first aperiodic set of tiles. It contains 20,426 Wang tiles, and although to us this number now seems extremely large, Berger's discovery was truly remarkable since it refuted Wang's conjecture that no aperiodic sets exist... Berger himself remarked that the number of tiles in his set is unnecessarily large and that he believed that some proper subset would also have the property of aperiodicity." Berger himself reduced the number of Wang tiles needed for aperiodicity to 104. The smallest set known at the time of Grunbaum & Shephard was 16. Most (all?) aperiodic tilings can be converted into sets of Wang tiles, although one must usually use more Wang tiles than tiles in the original aperiodic set. The Penrose tiles, for example, can be converted into a set of 24 Wang tiles. --Darrah Chavey Department of Math & Computer Science chavey@beloit.edu Beloit College; 700 College St; Beloit, Wisc. (608)-363-2220 http://www.beloit.edu/~chavey 53511 -- The main reason Santa is so jolly is because he knows where all the naughty girls live.