Complexity_ A Guided Tour - Melanie Mitchell [0]
Complexity
A Guided Tour
MELANIE MITCHELL
Oxford University Press, Inc., publishes works that further
Oxford University’s objective of excellence
in research, scholarship, and education.
Oxford New York
Auckland Cape Town Dar es Salaam Hong Kong Karachi
Kuala Lumpur Madrid Melbourne Mexico City Nairobi
New Delhi Shanghai Taipei Toronto
With offices in
Argentina Austria Brazil Chile Czech Republic France Greece
Guatemala Hungary Italy Japan Poland Portugal Singapore
South Korea Switzerland Thailand Turkey Ukraine Vietnam
Copyright © 2009 by Melanie Mitchell
The author is grateful to the following publishers for permission to reprint excerpts from the following works that appear as epigraphs in the book. Gödel, Escher, Bach: an Eternal Braid by Douglas R. Hofstadter, copyright © 1979 by Basic Books and reprinted by permission of the publisher. The Dreams of Reason by Heinz Pagels, copyright © by Heinz Pagels and reprinted by permission of Simon & Schuster Adult Publishing Group. Arcadia by Tom Stoppard, copyright © 1993 by Tom Stoppard and reprinted with permission of Faber and Faber, Inc., an affiliate of Farrar, Strauss & Giroux, LLC. “Trading Cities” from Invisible Cities by Italo Calvino, published by Secker and Warburg and reprinted by permission of The Random House Group Ltd. The Ages of Gaia: A Biography of Our Living Earth by James Lovelock, copyright © 1988 by The Commonwealth Fund Book Program of Memorial Sloan-Kettering Cancer Center and used by permission of W. W. Norton & Company, Inc. Mine the Harvest: A Collection of New Poems by Edna St. Vincent Millay, copyright © 1954, 1982 by Norma Millay Ellis and reprinted by permission of Elizabeth Barnett, Literary Executor, the Millay Society. “Trading Cities” from Invisible Cities by Italo Calvino, copyright © 1972 by Giulio Einaudi editore s.p.a., English translation by William Weaver, copyright © 1974 by Houghton Mifflin Harcourt Publishing Company, and reprinted by permission of the publisher. Complexity: Life at the Edge of Chaos by Roger Lewin, copyright © 1992, 1999 by Roger Lewin and reprinted by permission of the author.
Published by Oxford University Press, Inc.
198 Madison Avenue, New York, New York 10016
www.oup.com
Oxford is a registered trademark of Oxford University Press
All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior permission of Oxford University Press.
Library of Congress Cataloging-in-Publication Data
Mitchell, Melanie.
Complexity: a guided tour/Melanie Mitchell.
p. cm.
Includes bibliographical references and index.
ISBN 978-0-19-512441-5
1. Complexity (Philosophy) I. Title.
Q175.32.C65M58 2009
501—dc22 2008023794
9 8 7 6 5 4 3 2 1
Printed in the United States of America
on acid-free paper
To Douglas Hofstadter and John Holland
CONTENTS
Preface
Acknowledgments
PART ONE Background and History
CHAPTER ONE What Is Complexity?
CHAPTER TWO Dynamics, Chaos, and Prediction
CHAPTER THREE Information
CHAPTER FOUR Computation
CHAPTER FIVE Evolution
CHAPTER SIX Genetics, Simplified
CHAPTER SEVEN Defining and Measuring Complexity
PART TWO Life and Evolution in Computers
CHAPTER EIGHT Self-Reproducing Computer Programs
CHAPTER NINE Genetic Algorithms
PART THREE Computation Writ Large
CHAPTER TEN Cellular Automata, Life, and the Universe
CHAPTER ELEVEN Computing with Particles
CHAPTER TWELVE Information Processing in Living Systems
CHAPTER THIRTEEN How to Make Analogies (if You Are a Computer)
CHAPTER FOURTEEN Prospects of Computer Modeling
PART FOUR Network Thinking
CHAPTER FIFTEEN The Science of Networks
CHAPTER SIXTEEN Applying Network Science to Real-World Networks
CHAPTER SEVENTEEN The Mystery of Scaling
CHAPTER EIGHTEEN Evolution, Complexified
PART FIVE Conclusion
CHAPTER NINETEEN The Past and Future of the Sciences of Complexity