The Pattern On The Stone: The Simple Ideas That Make Computers Work

Grateful acknowledgment is made for permission from the following: Illustration of the macaque visual cortex from “Distributed Hierarchical Processing in Primate Cerebral Cortex,” Cerebral Cortex 1: 1–47, courtesy of Oxford University Press. Pablo Picasso’s Bernard Picasso with His Mother (1959); © 1998 Estate of Pablo Picasso/Artist Rights Society (ARS), New York. Photo of the Tinker Toy computer courtesy of The Computer Museum. The Science Masters Series is a global publishing venture consisting of original science books written by leading scientists and published by a worldwide team of twenty-six publishers assembled by John Brockman. The series was conceived by Anthony Cheetham of Orion Publishers and John Brockman of Brockman, Inc., a New York literary agency, and developed in coordination with Basic Books. The Science Masters name and marks are owned by and licensed to the publisher by Brockman Inc. Copyright © 1998 by W. D. Hillis. Published by Basic Books, A Member of the Perseus Books Group All rights reserved. No part of this book may be used or reproduced in any manner whatsoever without written permission except in the case of brief quotations embodied in critical articles and reviews. For information address Basic Books, 387 Park Avenue South, New York, NY 10016-8810. FIRST PAPERBACK EDITION 1999 Illustrations by Patricia Isaacs, Parrot Graphics Library of Congress Cataloging-in-Publication Data Hillis, W. Daniel. The pattern on the stone : the simple ideas that make computers work / W. Daniel Hillis.—1st ed. p. cm.—(Science masters) Includes index. ISBN-13: 978-0-465-06687-2 1. Computers. I. Title. II. Series: Science masters series. QA76.5.H4918 1998 004—dc21 98-38888 CIP CONTENTS Preface: Magic in the Stone 1 Nuts and Bolts 2 Universal Building Blocks 3 Programming 4 How Universal Are Turing Machines? 5 Algorithms and Heuristics 6 Memory: Information and Secret Codes 7 Speed: Parallel Computers 8 Computers That Learn and Adapt 9 Beyond Engineering Further Reading Acknowledgments Index PREFACE: MAGIC IN THE STONE I etch a pattern of geometric shapes onto a stone. To the uninitiated, the shapes look mysterious and complex, but I know that when arranged correctly they will give the stone a special power, enabling it to respond to incantations in a language no human being has ever spoken. I will ask the stone questions in this language, and it will answer by showing me a vision: a world created by my spell, a world imagined within the pattern on the stone. A few hundred years ago in my native New England, an accurate description of my occupation would have gotten me burned at the stake. Yet my work involves no witchcraft; I design and program computers. The stone is a wafer of silicon, and the incantations are software. The patterns etched on the chip and the programs that instruct the computer may look complicated and mysterious, but they are generated according to a few basic principles that are easily explained. Computers are the most complex objects we human beings have ever created, but in a fundamental sense they are remarkably simple. Working with teams of only a few dozen people, I have designed and built computers containing billions of active parts. The wiring diagram of one of these machines, if it were ever to be drawn, would fill all the books in a good-sized public library, and nobody would have the patience to scan the whole of it. Fortunately, such a diagram is unnecessary, because of the regularity of a computer’s design. Computers are built up in a hierarchy of parts