From Jones and Bartlett, a book on Stem Cells from Dr. Ann A. Kiessling and Scott C. Anderson:

Selected Articles:

May 30, 2007

Nano Computers, Part 1

You think your iPod is small? How about a computer the size of a molecule?

By Scott C. Anderson

A computer the size of a molecule? Okay, a fairly simple-minded computer and a pretty gnarly molecule, but it’s still a nice trick. Some of these nano-computers are being designed to be injected into your bloodstream. Based on what it finds there, it will make a medical diagnosis and then deliver the appropriate remedy in the form of a drug or a protein – a doctor and a pharmacy all wrapped up in a single molecule. No more waiting rooms, freezing exam tables, rude poking or long lines at the drugstore. Make way for a new world of really smart drugs.

The story of how science got here is fascinating, but somewhat convoluted. So, I’m going to break the story into three acts. For a little background, we need to start with a topic that seems totally unrelated: tiles.

Tiles? Yes; floor tiles, church tiles, bathroom tiles – you name it. Strange as it seems, with the right-shaped tiles you can actually create “visual programs.” Stick with me for a few minutes and I’ll show you how.

From the 700s to the 1400s, Islamic cultures produced artists and mathematicians of great talent and skill. Because Islam frowns on producing images of living things, Muslim artists found expression in abstract tiling, mixing math and art to great effect.

They created periodic motifs, a group of tiles which were repeated over and over. The effect was suggestive of infinity, and was designed to put the viewer into a humble, reflective mood. They quickly determined that repeating tiles can have 3-, 4- or 6-fold symmetry, but not, for instance, 5-fold or 7-fold symmetry. You can tile a flat area with triangles, squares or hexagons, but not with pentagons – they leave gaps in the pattern:

Of course, there's no law that says you're limited to one shape when you tile. In the 1200s, Islamic architecture started to incorporate sets of differently shaped tiles called girih that could fill the gaps in pentagonal tilings and create five-fold symmetries:

At first, the designs were not always perfect, and holes were sometimes created that couldn't be filled with the tile set (the one above uses 6 basic shapes). That was typically deemed to be a good place for a door or a window. But soon they found a way to mark the tiles so they could only fit together one way, and that particular way guaranteed a nice pattern with no holes.

Oddly enough, while these tiles filled the suface adequately, the patterns were not pefectly repeating. From a central point, they radiated out with similar -- but not exact -- duplication. That slight shift as the tiles spread out gave rise to a secondary motif. A person viewing the mosaic from several meters away would see a pattern that looked similar to the close-up view. Today we would call that a fractal, but it must have seemed quite magical in the thirteenth century. These were all very exciting extensions of the idea of infinity: not only was infinity of space suggested by repetition and scaling, but infininty of design was suggested by the subtle differences as the pattern unfolded.

And then, like many wonderful ideas in history, the insights that led to this amazing tiling just seemed to vanish for hundreds of years.

In the 1600s, the astronomer Johannes Kepler started playing with tiles as a way to visualize crystal structure (back in those days, astronomers were allowed to think about crystals). Like many before him, he quickly got frustrated with the limitations of repeating a single tile. Like the Persians, but apparently independently, he added new shapes to his repertoire. This led him to discover (or rediscover) unexpected symmetries. He created the “impossible” five-fold symmetry, for instance, by combining pentagons, stars and decagons:

Unlike the Persian mosaics, these tilings are perfectly periodic -- you can slide the basic pattern around a specific distance (the period) and it will match up exactly with the rest of the pattern. Kepler found a large set of tiles that could be laid periodically. In fact, given a set of tiles that fit together nicely on a flat surface, you ought to be able to create an infinitude of different periodic patterns. It seemed that the laws of tiling had been solved, and they were simple and obvious.

Proving the Obvious

So obvious that in 1961, when the mathematician Hao Wang wanted to prove an algorithm about tiles, he assumed that if you could physically lay down a set of tiles, you could always do it periodically. To prove it, Wang created a set of square tiles with colored edges that had to be placed so that their colors matched. Here's a sample group of 13 Wang tiles:

To Wang’s amazement, he found that these tiles could easily lead to dead ends. Either he had to break the color-matching rule or he had to stop tiling. Wang was beginning to develop doubts about his thesis, and started to believe that his assertion was actually unprovable.

Five years later, Robert Berger proved that, in fact, certain sets of Wang tiles could never have a periodic tiling. It wasn't easy to show this, mind you. Berger had to create a set of 20,426 tiles to make his point! (A certain amount of dogged determinism is handy in this field of math.)

In the early 1970s, the brilliant mathematical physicist Roger Penrose came up with several smaller sets of patterned tiles that also refused to fit into periodic patterns. As with the Wang tiles, these tiles came with rules: they had to match at the edges. A particularly nice set had two simple tiles that Penrose called darts and kites. There is only one way to fit them so that the pattern matches:

Two Penrose tiles

The right fit.
The wrong fit.

It turns out that no matter how you put these kites and darts together, they will never make a repeating pattern (even though they vaguely seem to). Notice that these particular Penrose tiles are all four-sided, but the arrangement around the central star yields a five-fold radial symmetry. That means you can turn it 72 degrees (360° / 5) and it will look just the same:

The particular grouping of tiles around the center is never repeated again, so the pattern is non-periodic. If you are sensing deja-vu, you are right. This is just like the Persian tiling we saw before, although Roger Penrose didn't know it at the time.

Pure mathematicians love stuff like this – patterns that aren't really patterns, impossible symmetries and things that are generally so abstract they couldn't possibly have a physical counterpart. It's strictly a head-trip, totally theoretical and certainly not relevant to the real world. Thankfully, these mathematical monstrosities were safely confined to the Annals of Mathematical Obscurity. Or so everyone thought.

Impossible symmetry found in Nature!

In 1982, Dan Shechtman was looking at an x-ray diffraction diagram, as he had done hundreds of times before, when he did a classic double-take. Knowing, as all material scientists do, that crystals only come in 3-, 4- and 6-fold symmetry, he was astonished to see a ten-fold crystal unmistakably depicted in a diffraction image:

original image...
enhanced to show symmetry

It was a weird crystal, to be sure: an alloy of aluminum and manganese. But its diffraction pattern was nonetheless completely impossible, and he knew it. Everyone knew it. For one thing, with a ten-fold symmetry, it couldn't be periodic, and everyone knew that crystals were periodic. More importantly, no one had seen anything like it in 70 years of x-ray diffraction work. Something was wrong, that was crystal-clear, but Shechtman persisted. After two years of convincing both himself and the scientific establishment, he finally published his landmark paper.

To honor his perseverance, Shechtman was awarded the 1999 Wolf Prize in Physics "for the experimental discovery of quasi-crystals, non-periodic solids having long-range order, which inspired the exploration of a new fundamental state of matter." It wasn't long before people realized that Penrose's abstract tiles could explain this unusual atomic behavior. Ah, so much for pure math.

Penrose and Wang tiles are interesting, because they have to satisfy both form and function. Form because they must fit snugly together, and function because they must match a pattern. It's the function that starts to hint at the ability of tiles to compute.

Here is how tiling is like computing: following the rules of color coding to pick the next tile is not all that different from using computer code to execute a program. In one case you have coloring rules for laying out tiles, in the other case you have computer instructions for manipulating bits.

The tiling rules are straight-forward: the edge of each tile specifies what can be placed next to it. This turns out to be a kind of computer called a Turing machine, after Alan Turing, who showed that such a machine is the equivalent of a general-purpose computer. Turing went on to demonstrate that, in general, computer programs could not be trusted to know when to quit. Novice programmers who have created their first infinite loop know exactly what that means. But it turns out to be a deep, fundamental problem of computing, blandly titled “the halting problem.” No matter how much you think you know about your program, if it's sufficiently complicated, there is no guarantee that it will ever halt and actually deliver a solution.

For a programmer, this really stinks, because you can never be positive that your program won’t crash or hang. With our lives increasingly dependent on software, this is a sobering thought. But I digress.

With tiles, the equivalent of halting is finishing a finite pattern, where there are no more valid tiles that can be laid. If, on the other hand, you can't finish a pattern because it simply goes on and on, you have a halting problem. And since these tiles are actually Turing machines, and since you can never be sure a Turing machine will stop, you can therefore never know if a tiling will be periodic. (I won’t blame you for re-reading this paragraph). Score another point for “abstract” mathematics.

Living with Uncertainty

That uncertainty sounds pretty ominous, but the halting problem has never stopped a programmer before. Besides, the more interesting revelation is that tiling can actually be equivalent to computing. That’s not at all obvious, but pretty cool. So far this has all been quite abstract, so let's actually use tiles to compute a sum:

For our computer, we'll use four counting tiles and three “scaffold” tiles, forming a base and an upright. This rather arbitrary structure will draw the boundaries for our computer. Our computer is binary, so you might think two counting tiles would do (0 and 1), but we need to add, so we have to deal with a carry. For that, we toss in another two tiles to indicate whether there is a carry that goes along with the bit or not.

The computer starts with the S tile in the lower right corner. The base scaffold (B) and the edge scaffold (E) will "prime the pump" and start out the calculations properly. Notice that after the first E and B tiles are placed next to the S tile, there is only one choice for the first counting tile, namely a 1 with blue on the right and gray on the bottom. As the tiles are filled in from the bottom up, you can read a series of numbers in each row. The sequence (from bottom to top) goes 1, 10, 11, 100, 101, etc., which are the numbers one through five in binary. So this simple tiling computer is able to add one to the number in a row and print the answer in the next row. Basically, it counts. It's not exotic, but it's a pretty good trick for a handful of colored tiles.

You can see where this tiling sequence is going. It will keep on adding one forever, thus counting to infinity. Since the number keeps growing, this tile pattern is never going to repeat. Finally we have our tile computer! It’s decidedly impractical, but for a simple arrangement of bathroom tiles, it’s strangely powerful.

And now for a short break

That's the end of part 1. In Nano Computers, Part 2, we'll discuss how to make molecular tinker toys from “sticks” of DNA. From there it’s just another quick hop to injectable molecular computers…

Copyright © 2000-2014 by Scott Anderson
For reprint rights, email the author:

Here are some other suggested readings about mathematical tiling: