|
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:
|
|
|
|
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:
Scott_Anderson@ScienceForPeople.com
Here are some other suggested readings about mathematical tiling:
|
|
