1: The Turing Machine
So, Wednesday I looked at Wikipedia's front page and saw, under the "On
this day" heading:
1936 – English mathematician Alan Turing
published the first details of the Turing machine (model
pictured), an abstract device that can simulate the logic of any computer
algorithm by manipulating symbols.
It was the ""model pictured" that grabbed me. The caption was/is "A physical
Turing machine model. A true Turing machine would have unlimited tape on
both sides, however, physical models can only have a finite amount of
tape."
I knew that -- everyone who studies computer science knows that, and a few
have dreamed, as I had, of building a physical model. I even figured out
how to build one out of wood, minus a few details. But there it was.
(If you're not interested in the details, you can skip this and the other
indented blocks. But I digress...)
A Turing Machine is a remarkably simple device. It has a read head, a
write head, a strip of tape that they operate on, and a controller with a
finite number of states. It can read what's on the tape -- the classic
machine uses blank, "0", and "1". (Some versions use "X" instead of "1",
and some dispense with "0" and just have 1 and blank. That makes
programming them a little more complicated, but not by much. Some have
more symbols. It doesn't matter -- you can program around it.)
The machine can move the tape backward and forward. Numbers are usually
represented in Unary, so you count "1", "11", "111", ..., although with
both 1 and 0 you could use binary, and some versions do.
The machine has a "state", which selects a line in the machine's program
that tells it what to write, which direction to move the tape, and which
state to go to next, depending on what symbol the read head is looking at.
(Think of the table as a drum with pegs on it, like a music box.)
That's it. That's all you need to compute any function that can be
computed by any kind of mechanical or digital computer. Of course you
may need a lot of tape -- so you need to attach it to a tape factory --
and a lot of time.
The critical thing is that it's possible to design a universal
Turing machine: it takes a tape, and the state table of a Turing machine
(in 1's, 0's and blanks), and it uses that description to do exactly what
that machine is programmed to do. Turing's big accomplishment was using
the universal Turing machine to prove that there some things that a
computer can't do, no matter how much time and tape you give it.
But of course I was much more fascinated by the machines, starting at the website of the model that first
grabbed my attention., and proceeding to a Turing machine made
of legos. I spent some time in the Turing
machine gallery. But the rabbit hole went deeper than that.
2: The Universal Constructor
At about that point it ocurred to me to look at the Wikipedia page for the
Von Neumann universal constructor. Because once you have a kind of
machine that can simulate itself, the natural question is whether
you can have a machine that can build a copy of itself.
The trivial answer to this question is "Yes, of course. Cells have been
reproducing themselves for billions of years." But in the 1940s when von
Neumann was thinking about this, the structure of DNA had not yet been
determined -- that was 1953 -- and although it had been known since the late
1920s that DNA had something to do with heredity, nobody knew how it
worked. So his insight into the machinery of reproduction was pretty
remarkable.
Like Turing's insight into the machinery of computation, von Neumann's
insight into the machinery of reproduction was to separate the
machine -- the Universal Constructor -- from the description of
what it was to construct, stored on something simple -- a tape.
Von Neumann's machine was/is a cellular automaton; it "lived" (if you can
call it that) on a grid of squares, where each square can be in one of 29
different states, with rules that tell it what to do depending on the
states of its neighbors. A completely working machine wasn't simulated
until 1995. Its constructor had 6329 32-state cells, and a tape with a
length of 145,315. It took it over 63 billion timesteps to copy itself.
(Smaller and faster versions have been constructed since then).
At, say, 1000 steps/second, that would have taken over two years. It
wasn't until 2008 that a program, Golly, became
able to simulate it using the hashlife algorithm; it
now takes only a few minutes.
Which led me even further down the rabbit hole. Because no discussion of
cellular automata would be complete without Conway's
Game of Life.
3: The Game of Life
It's not really a game, of course, it's a cellular automaton. Each cell
in the square grid is either dead or alive. You start with an arrangement
of live cells, and turn them loose according to four simple rules:
- If a live cell has fewer than two live neighbors (out of the 8 cells
surrounding it), it dies of loneliness.
- A live cell with two or three live neighbors, stays alive.
- A live cell with more than three live neighbors dies of overpopulation.
- A dead cell with exactly three live neighbors becomes live.
I first encountered the game in the October 1970 issue of Scientific
American, in Martin Gardner's "Mathematical Games" column. The Wikipedia
article gives a good introduction.
Patterns in Life evolve in a bewildering variety of ways. Many of them
die out quickly -- an isolated cell, for example. Some patterns sit there
and do nothing -- they're called "still lifes". A 2x2 block of cells for
an example. Some blow up unpredictably, and may or may not leave a pile
of random still lifes behind. Some patterns oscillate: a horizontal row
of three cells will become a vertical row in the next turn, and vice versa
-- it's called a "blinker".
And some patterns move. The simplest, called a "glider", appears in this
post's icon. You can crash gliders into blocks or gliders into gliders,
and depending on the timing they will do different interesting things. It
didn't take people long to figure out that you can build computers,
including a universal Turing machine. Or a machine that prints out the
digits of Pi.
Or a universal constructor.
4: The universal constructor
While I was falling into this rabbit hole, I happened to remember a
passing mention of a universal constructor that can build anything at all out of exactly 15
gliders. (Strictly speaking, anything that can be constructed by
crashing gliders together. Some patterns can't be made that way. But
almost all the complicated and interesting ones that people are building
these days can.) If this intrigues you, go read the article. Or wait
until the next section, where I finally get to the bottom of the rabbit
hole.
On the way down I encountered lots of weird things -- the aforementioned
universal Turing machine and Pi printer, and a variety of "spaceships"
that travel by, in effect, repeatedly constructing a new copy of
themselves, then cleaning up the old copy. It took a while for me to get
my head around that.
Then, sometime Wednesday evening, I found the book.
5: The Book of Life
It's not called "The Book of Life", of course, it's called Conway's Game of Life: Mathematics
and Construction. But you get the idea. You can download the PDF.
The book ends with a pattern that simulates a Life cell. There are
several different versions of this; this is the latest. It works by
making copies of itself in any neighboring cells that are coming alive,
then destroying itself if it's about to die. Wild.
Another fine post from
The Computer Curmudgeon (also at
computer-curmudgeon.com).
Donation buttons in profile.
