Stephen Wolfram's: A New Kind of Science | Online
Jump to Page
Look Up in Index
Search

Chapter 5 Notes > Section 7 > Page 943 > Note (d) Previous note-----Next note
Notes for: Two Dimensions and Beyond | Systems Based on Constraints


*Polyominoes

An example of a tiling problem that is in some respects particularly close to the grid-based constraint systems discussed in the main text concerns covering the plane with polyominoes that are formed by gluing collections of squares together. Tiling by polyominoes has been investigated since at least the late 1950s, particularly by Solomon Golomb, but it is only very recently that sets of polyominoes which force non-periodic patterns have been found. The set (a) below was announced by Roger Penrose in 1994; the slightly smaller set (b) was found by Matthew Cook as part of the development of this book.


Both of these sets yield nested patterns. Steps in the construction of the pattern for set (b) are shown below. At stage n the number of polyominoes of each type is Fibonacci[2n-{2,0,1}]/{1,2,1}. Set (a) works in a roughly similar way, but with a considerably more complicated recursion.






PAGE IMAGE

Page image

RELATED LINKS

Pages related to this note:

*

All notes on this page:

* Relation to 2D cellular automata
* Relation to 1D cellular automata
* Non-computable [2D] patterns
* Tiling [problems]
* Polyominoes
* All notes for this section
* Downloadable programs for this page
* Downloadable images
* Search Forum for this page
* Post a comment
* NKS | Online FAQs
From Stephen Wolfram: A New Kind of Science [citation] Previous note-----Next note