math

The new [physics-based] viewpoint is so potent that it has perhaps, caused too many metallurgists to forsake their partially intuitive knowledge of the nature of materials to worship at the shrine of mathematics, a trend reinforced by the curious human tendency to laud the more abstract.

Even more than Euclid, hath Euler gazed on beauty bare.

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.

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.