DIGITIZED This page intentionally left blank The science of computers and how it shapes our world Peter J. Bentley (cid:20) 3 Great Clarendon Street, Oxford ox2 6dp Oxford University Press is a department of the University of Oxford. It furthers the University’s objective of excellence in research, scholarship, and education by publishing worldwide in 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 offi ces in Argentina Austria Brazil Chile Czech Republic France Greece Guatemala Hungary Italy Japan Poland Portugal Singapore South Korea Switzerland Thailand Turkey Ukraine Vietnam Oxford is a registered trade mark of Oxford University Press in the UK and in certain other countries Published in the United States by Oxford University Press Inc., New York © Peter J. Bentley 2012 The moral rights of the author have been asserted Database right Oxford University Press (maker) First Edition 2012 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, without the prior permission in writing of Oxford University Press, or as expressly permitted by law, or under terms agreed with the appropriate reprographics rights organization. Enquiries concerning reproduction outside the scope of the above should be sent to the Rights Department, Oxford University Press, at the address above You must not circulate this book in any other binding or cover and you must impose the same condition on any acquirer British Library Cataloguing in Publication Data Data available Library of Congress Cataloguing in Publication Data Data available Typeset by SPI Publisher Services, Pondicherry, India Printed in Great Britain on acid-free paper by Clay’s Ltd, St Ives plc ISBN 978–0–19–969379–5 10 9 8 7 6 5 4 3 2 1 CONTENTS A cknowledgements xi L ist of Illustrations xiii 0 00 Introduction 1 Computers uncovered 4 The science of computers 8 0 01 Can You Compute? 13 Understanding the impossible 1 6 Turing’s unstoppable machines 2 1 Turing’s legacy 25 Complexity is simple 2 9 Does P = NP? 34 Oracles and other complexities 3 8 Theoretical futures 41 0 10 Disposable Computing 43 Thinking logically 4 5 Building brains 4 9 Anatomy of a digital brain 54 The end of the beginning 5 8 The Law of Moore 62 contents The future is many 67 Beyond von Neumann 7 1 0 11 Your Life in Binary Digits 74 Learning to program computers 8 0 Climbing higher 85 Bases for data 91 Software crisis 9 5 Virtual futures 1 02 1 00 Monkeys with World-Spanning Voices 104 Diverse connections 1 08 Inter-networking 1 12 Addressing for success 1 19 Spinning webs over networks 1 23 Weaving tangled webs 1 29 Webs of deceit 1 34 Digital lives 1 37 1 01 My Computer Made Me Cry 1 40 The birth of friendly computing 1 45 Seeing with new eyes 1 49 Photos and chicken wire 153 Waking dreams 1 56 It’s not what you do but the way that you do it 162 My pet computer 168 Human–computer integration 1 70 1 10 Building Bionic Brains 1 73 Teaching computers how to play 175 The birth of intelligence 1 79 vi contents The seasons of AI 1 82 Intelligence from feet to head 1 90 Adaptation by natural selection 1 95 Learning to learn, predicting the predictors 2 01 Complex futures 205 1 11 A Computer Changed My Life 209 Computer creativity 210 Computational biology 2 18 Computer medicine 225 Computer detectives 233 Endnotes 241 Bibliographic Notes 263 Index 285 vii This page intentionally left blank In 2010 the Department of Computer Science, University College London, celebrated its 30 th anniversary. May it celebrate many more!