The pattern on the stone by William Daniel Hillis

This is a very well-written little book that explains the basic concepts of computer science in layman’s terms. If you don’t know how computers work but want to learn, this book is exactly what you’re looking for. It’s very easy to read without being misleading and explain things in very ingenious ways. For instance, in order to stress that there is nothing special about silicon-based transistors, he shows how the elementary logical functions that serve as the universal building blocks of computation can be implemented using all sorts of physical systems, such as water pipes and hydraulic valves. Indeed, while he was a student at MIT, Hillis built a computer that plays tic-tac-toe entirely from tinker toys. The book also discusses more advanced topics, but always in a very accessible way. For instance, here is a passage where he talks about genetic programming, which really blew my mind when I read it because I had never heard of this before:

So, in creating an artificial intelligence, what is the alternative to engineering? One approach is to mimic within the computer the process of biological evolution. Simulated evolution gives us a different way to design complicated hardware and software—a way that avoids many of the problems of engineering. To understand how simulated evolution works, let’s look at a specific example. Say that we want to design a piece of software that sorts numbers into descending order. The standard engineering approach would be to write such a program using one of the sorting algorithms discussed in chapter 5, but let’s consider how we might instead “evolve” the software.

The first step is to generate a “population” of random programs. We can create this population using a pseudorandom number generator to produce random sequences of instructions (see chapter 4). To speed up the process, we can use only those instructions useful for sorting, such as comparison and exchange instructions. Each of these random sequences of instructions is a program: the random population will contain, say, 10,000 such programs, each one a few hundred instructions long.

The next step is to test the population to find which programs are the most successful. This requires us to run each of the programs to see whether or not it can sort a test sequence correctly. Of course, since the programs are random, none are likely to pass the test—but by sheer luck some will come closer to a correct sorting than others. For instance, by chance, a program may move low numbers to the back of the sequence. By testing each program on a few different number sequences, we can assign a fitness score to each program.

The next step is to create new populations descended from the high-scoring programs. To accomplish this, programs with less than average scores are deleted; only the fittest programs survive. The new population is created by making copies of the surviving programs with minor random variations, a process analogous to asexual reproduction with mutation. Alternatively, we can “breed” new programs by pairing survivors in the previous generation—a process analogous to sexual reproduction. We accomplish this by combining instruction sequences from each of the “parent” programs to produce a “child.” The parents presumably survived because they contained useful instruction sequences, and there is a good chance that the child will inherit the most useful traits from each of the parents.

When the new generation of programs is produced, it is again subjected to the same testing and selection procedure, so that once again the fittest programs survive and reproduce. A parallel computer will produce a new generation every few seconds, so the selection and variation processes can feasibly be repeated many thousands of times. With each generation, the average fitness of the population tends to increase—that is, the programs get better and better at sorting. After a few thousand generations, the programs will sort perfectly.

I have used simulated evolution to evolve a program to solve specific sorting problems, so I know that the process works as described. In my experiments, I also favored the programs that sorted the test sequences quickly, so that faster programs were more likely to survive. This evolutionary process created very fast sorting programs. For the problems I was interested in, the programs that evolved were actually slightly faster than any of the algorithms described in chapter 5—and, in fact, they were faster at sorting numbers than any program I could have written myself.

One of the interesting things about the sorting programs that evolved in my experiment is that I do not understand how they work. I have carefully examined their instruction sequences, but I do not understand them: I have no simpler explanation of how the programs work than the instruction sequences themselves. It may be that the programs are not understandable—that there is no way to break the operation of the program into a hierarchy of understandable parts. If this is true—if evolution can produce something as simple as a sorting program which is fundamentally incomprehensible—it does not bode well for our prospects of ever understanding the human brain. 

What Hillis describes in this passage is amazing in its own right, but here is another reason why I find that really fascinating. One reason to be skeptical that we’ll ever be able to create artificial intelligences that can rival our own is that, in order to do so, it may seem that we’d have to understand how our brain works first, so that we can reproduce it. But the human brain is probably the most complex system in the universe and it’s really unclear that we’ll ever be able to understand how it works in every detail, so it may be that we’ll never be able to create artificial intelligences that can rival our own, since you can’t design something after a system you don’t understand. However, the technique Hillis describes in this passage suggests that we may not have to understand how the human brain works in order to create artificial intelligences that rival its power, since we could just let it evolve in a process that imitates evolution in the natural world. I don’t really know anything about artificial intelligence, so I’m just telling you what I thought about back when I read this, which may be total nonsense. If you know good references about genetic programming and artificial intelligence in general,  please tell me about them in the comments.

4 thoughts

  1. Neural networks work in a similar way, but are much nicer because we don’t have to make the changes entirely at random: We can use calculus (that I don’t understand at all) to determine how to change the program. There are still problems like ensuring you have enough data (if you train on too small of a set, you might train your program to do something easier than what you want it to learn, like memorizing the answer), and making the program simple enough that you can run each step millions of times until it gets a decent answer. It’s incredibly powerful though.

    This is a good intro:

    1. Thanks for the link, I’ll read that later. I can see what this makes you think about neural networks, but it’s actually different, although I suppose the two approaches could presumably be combined and probably have been. With a neural network, you train the program with data and it adjusts on its own by changing the weights of the neurons in the network after each pass, but there is no analogue of reproduction.

  2. Interesting, but wouldn’t you learn more (and more deeply) by taking some computer science courses? I really distrust popularizations, because I know that in the fields I understand (mostly law, plus some subspecialities within economics and finance), popular accounts leave out a lot of subtleties.

    1. Well, I actually have a Bachelor in computer science, so I have already taken quite a few courses on computer science 🙂 But I never took any class on artificial intelligence and, at this point, I prefer to learn with books. I would definitely prefer a book that isn’t a popularization, but explains things in detail, though without assuming prior knowledge about artificial intelligence. I should say, however, that although Hillis’s book is a popularization, it’s really very good and even I who majored in computer science in college enjoyed it a lot.

Comments are closed.