fLYr1t\Ar1 Lee u T RL son (Ot\PUTATIOn Photograph courtesy of Michelle Feynman and Carl R. Feynman fcrnt\An LLCTURLS on (Ot\PUTATIOn RICMARD P. fern/'\An {DITH .DV TONV .Un • .hO.DIN W. .flll~N Department of Electronics and Computer Science University of Southampton England THE ADVANCED BOOK PROGRAM 0 CRC Press Taylor&Francis Group Boca Raton London New York CRC Press is an imprint of the Taylor & Francis Group, an informa business First published 1996 by Westview Press Published 2018 by CRC Press Taylor & Francis Group 6000 Broken Sound Parkway NW, Suite 300 Boca Raton, FL 33487-2742 CRC Press is an imprint oft he Taylor & Francis Group, an informa business Copyright © 1996 by Carl R. Feynman and Michelle Feynman Foreword and Afterword copyright © 1996 by Anthony J.G. Hey and Robin W. Allen No claim to original U.S. Government works This book contains information obtained from authentic and highly regarded sources. Reasonable efforts have been made to publish reliable data and information, but the author and publisher cannot assume responsibility for the validity of all materials or the consequences of their use. The authors and publishers have attempted to trace the copyright holders of all material reproduced in this publication and apologize to copyright holders if permission to publish in this form has not been obtained. If any copyright material has not been acknowledged please write and let us know so we may rectify in any future reprint Except as permitted under U.S. Copyright Law, no part of this book may be reprinted, reproduced, transmitted, or utilized in any form by any electronic, mechanical, or other means, now known or hereafter invented, including photocopying, microfilming, and recording, or in any information storage or retrieval system, without written permission from the publishers. Trademark Notice: Product or corporate names may be trademarks or registered trademarks, and are used only for identification and explanation without intent to infringe. Visit the Taylor & Francis Web site at http:jjwww.taylorandfrancis.com and the CRC Press Web site at http:jjwww.crcpress.com A Cataloging-in-Publication record for this book is available from the Library of Congress. Text desigo and typesetting by Tony Hey ISBN 13: 978-().7382-0296-9 (pbk) CONTENTS Foreword viii Preface (Richard Feynman) xiii 1 Introduction to Computers 1 1.1 The File Clerk Model 5 1.2 Instruction Sets 8 1.3 Summary 17 2 Computer Organization 20 2.1 Gates and Combinational Logic 20 2.2 The Binary Decoder 30 2.3 More on Gates: Reversible Gates 34 2.4 Complete Sets of Operators 39 2.5 Flip-Flops and Computer Memory 42 2.6 Timing and Shift Registers 46 3 The Theory of Computation 52 3.1 Effective Procedures and Computability 52 3.2 Finite State Machines 55 3.3 The Limitations of Finite State Machines 60 3.4 Turing Machines 66 3.5 More on Turing Machines 75 3.6 Universal Turing Machines and the Halting Problem 80 3.7 Computability 88 v vi CONTENTS 4 Coding and Information Theory 94 4.1 Computing and Communication Theory 95 4.2 Error Detecting and Correcting Codes 95 4.3 Shannon's Theorem 106 4.4 The Geometry of Message Space 110 4.5 Data Compression and Information 115 4.6 Information Theory 120 4.7 Further Coding Techniques 123 4.8 Analogue Signal Transmission 129 5 Reversible Computation and the Thermodynamics of Computing 137 5.1 The Physics of Information 137 5.2 Reversible Computation and the Thermodynamics of Computing 151 5.3 Computation: Energy Cost versus Speed 167 5.4 The General Reversible Computer 172 5.5 The Billiard Ball Computer 176 5.6 Quantum Computation 182 6 Quantum Mechanical Computers 185 (Reprinted from Optics News, February 1985) 6.1 Introduction 185 6.2 Computation with a Reversible Machine 187 6.3 A Quantum Mechanical Computer 191 6.4 Imperfections and Irreversible Free Energy Loss 199 6.5 Simplifying the Implementation 202 6.6 Conclusions 210 6.7 References 211 CONTENTS vii 7 Physical Aspects of Computation 212 A Caveat from the Editors 212 7.1 The Physics of Semiconductor Devices 213 7.2 Energy Use and Heat Loss in Computers 238 7.3 VLSI Circuit Construction 257 7.4 Further Limitations on Machine Design 274 Afterword: Memories of Richard Feynman 284 Suggested Reading 294 Index 297 Editor's Foreword Since it is now some eight years since Feynman died I feel it necessary to explain the genesis of these 'Feynman Lectures on Computation'. In November 1987 I received a call from Helen Tuck, Feynman's secretary of many years, saying that Feynman wanted me to write up his lecture notes on computation for publication. Sixteen years earlier, as a post-doc at CalTech I had declined the opportunity to edit his 'Parton' lectures on the grounds that it would be a distraction from my research. I had often regretted this decision so I did not take much persuading to give it a try this time around. At CalTech that first time, I was a particle physicist, but ten years later, on a sabbatical visit to CalTech in 1981, I became interested in computational physics problems -playing with variational approaches that (I later found out) were similar to techniques Feynman had used many years before. The stimulus of a CalTech colloquium on 'The Future of VLSI' by Carver Mead then began my move towards parallel computing and computer science. Feynman had an interest in computing for many years, dating back to the Manhattan project and the modeling of the plutonium implosion bomb. In 'Los Alamos from Below', published in 'Surely You're Joking, Mr. Feynman!', Feynman recounts how he was put in charge of the 'IBM group' to calculate the energy release during implosion. Even in those days before the advent of the digital computer, Feynman and his team worked out ways to do bomb calculations in parallel. The official record at CalTech lists Feynman as joining with John Hopfield and Carver Mead in 1981 to give an interdisciplinary course entitled 'The Physics of Computation'. The course was given for two years and John Hopfield remembers that all three of them never managed to give the course together in the same year: one year Feynman was ill, and the second year Mead was on leave. A handout from the course of 1982/3 reveals the flavor of the course: a basic primer on computation, computability and information theory followed by a section entitled 'Limits on computation arising in the physical world and "fundamental" limits on computation'. The lectures that year were given by Feynman and Hopfield with guest lectures from experts such as Marvin Minsky, John Cocke and Charles Bennett. In the spring of 1983, through his connection with MIT and his son Carl, Feynman worked as a consultant for Danny Hillis at Thinking Machines, an ambitious, new parallel computer company. In the fall of 1983, Feynman first gave a course on computing by himself, listed in the CalTech record as being called 'Potentialities and Limitations of EDITOR'S FOREWORD ix Computing Machines'. In the years 1984/85 and 1985/86, the lectures were taped and it is from these tapes and Feynman' s notebooks that these lecture notes have been reconstructed. In reply to Helen Tuck, I told her I was visiting CalTech in January of 1988 to talk at the 'Hypercube Conference'. This was a parallel computing conference that originated from the pioneering work at CalTech by Geoffrey Fox and Chuck Seitz on their 'Cosmic Cube' parallel computer. I talked with Feynman in January and he was very keen that his lectures on computation should see the light of day. I agreed to take on the project and returned to Southampton with an agreement to keep in touch. Alas, Feynman died not long after this meeting and we had no chance for a more detailed dialogue about the proposed content of his published lectures. Helen Tuck had forwarded to me both a copy of the tapes and a copy of Feynman's notes for the course. It proved to be a lot of work to put his lectures in a form suitable for publication. Like the earlier course with Hopfield and Mead, there were several guest lecturers giving one or more lectures on topics ranging from the programming language 'Scheme' to physics applications on the 'Cosmic Cube'. I also discovered that several people had attempted the task before me! However, the basic core of.Feynman's contribution to the course rapidly became clear - an introductory section on computers, followed by five sections exploring the limitations of computers arising from the structure of logic gates, from mathematical logic, from the unreliability of their components, from the thermodynamics of computing and from the physics of semiconductor technology. In a sixth section, Feynman discussed the limitations of computers due to quantum mechanics. His analysis of quantum mechanical computers was presented at a meeting in Anaheim in June of 1984 and subsequently published in the journal 'Optics News' in February 1985. These sections were followed by lectures by invited speakers on a wide range of 'advanced applications' of computers - robotics, AI, vision, parallel architectures and many other topics which varied from year to year. As advertised, Feynman's lecture course set out to explore the limitations and potentialities of computers. Although the lectures were given some ten yeats ago, much of the material is relatively·'timeless' and represents a Feynmanesque overview of some standard topics in computer science. Taken as a whole, however, the course is unusual and genuinely interdisciplinary. Besides giving the 'Feynman treatment' to subjects such as computability, Turing machines (or as Feynman says, 'Mr. Turing's machines'), Shannon's theorem and information theory, Feynman also discusses reversible computation, thermodynamics and quantum computation. Such a wide-ranging discussion of the fundamental basis of computers is undoubtedly unique and a 'sideways', Feynman-type view of the