Wang tiles (Hao Wang, 1961) are a class of formal systems. They are modelled visually by square tiles with a color on each side. A set of such tiles is selected, and copies of the tiles are arranged side by side with matching colors, without rotating or reflecting them.
The basic question about a set of Wang tiles is whether it can tile the plane or not, i.e., whether an entire infinite plane can be filled this way. The next question is whether this can be done in a periodic pattern.
In 1966, Wang’s student Robert Berger solved the problem in the negative. He proved that no algorithm for the problem can exist, by showing how to translate any Turing machine into a set of Wang tiles that tiles the plane if and only if the Turing machine does not halt. The undecidability of the halting problem then implies the undecidability of Wang’s tiling problem.
A tree is a kind of graph, but a graph can be considerably more complex than a tree.
I have reason to believe, which for brevity’s sake I will treat elsewhere, that the most complex class of processes and structures we humans can consciously prescribe, reduces mathematically to a tree. A tree has a top, bottom, left and right. Its branches fan out from the trunk and they don’t intersect with one another. They are discrete, contiguous, identifiable objects which persist across time. Trees are Things.
Software and websites, however, reduce to arbitrarily more complex structures: they are graphs. A graph has no meaningful orientation whatsoever. No sequence, no obvious start or end—at least none that we can intuit. It is better considered not as one Thing, but as a federation of Things, like the brain or a fungus network, or perhaps a composite artifact left behind from an ongoing process, like an ant colony or human city.
The tree of my title is not a green tree with leaves. It is the name of an abstract structure. I shall contrast it with another, more complex abstract structure called a semilattice.
Both the tree and semilattice are ways of thinking about how a large collection of many small systems goes to make up a large and complex system.
A collection of sets forms a semilattice if, and only if, when two overlapping sets belong to the collection, the set of elements common to both also belongs to the collection. That is, if [234] and [345] belong to the collection, then [34] belongs to the collection.
A collection of sets forms a tree if, and only if, for any two sets that belong to the collection either one is wholly contained in the other, or they are wholly disjoint. Every tree is trivially a simple semilattice.
We are concerned with the difference between structures in which no overlap occurs, and those structures in which overlap does occur.
The semilattice is potentially a much more complex and subtle structure than a tree. It is this lack of structural complexity, characteristic of trees, which is crippling our conceptions of the city.
A translation is given of Truchet’s 1704 paper showing that an infinity of patterns can be generated by the assembly of a single half—colored tile in various orientations.
This paper introduces a novel representation, called the InfoCrystal, that can be used as a visualization tool as well as a visual query language to help users search for information. The InfoCrystal visualizes all the possible relationships among N concepts.
One of the best (and easiest) ways to start making sense of a document is to highlight its “important” words, or the words that appear within that document more often than chance would predict. That’s the idea behind Amazon.com’s “Statistically Improbable Phrases”:
Amazon.com’s Statistically Improbable Phrases, or “SIPs”, are the most distinctive phrases in the text of books in the Search Inside!™ program. To identify SIPs, our computers scan the text of all books in the Search Inside! program. If they find a phrase that occurs a large number of times in a particular book relative to all Search Inside! books, that phrase is a SIP in that book.