Feynman Lectures on Computation

From 1983 to 1986, the legendary physicist and teacher Richard Feynman gave a course at Caltech called “Potentialities and Limitations of Computing Machines.”Although the lectures are over ten years old, most of the material is timeless and presents a “Feynmanesque” overview of many standard and some not-so-standard topics in computer science. These include computability, Turing machines (or as Feynman said, “Mr. Turing’s machines”), information theory, Shannon’s Theorem, reversible computation, the thermodynamics of computation, the quantum limits to computation, and the physics of VLSI devices. Taken together, these lectures represent a unique exploration of the fundamental limitations of digital computers.Feynman’s philosophy of learning and discovery comes through strongly in these lectures. He constantly points out the benefits of playing around with concepts and working out solutions to problems on your own-before looking at the back of the book for the answers. As Feynman says in the lectures: “If you keep proving stuff that others have done, getting confidence, increasing complexities of your solutions-for the fun of it-then one day you’ll turn around and discovers that nobody actually did that one! And that’s the way to become a computer scientist.” Title page......Page 5 Contents......Page 7 Foreword......Page 10 Preface (Richard Feynman)......Page 15 1. Introduction to Computers......Page 17 1.1 The File Clerk Model......Page 21 1.2 Instruction Sets......Page 24 1.3 Summary......Page 33 2.1 Gates and Combinational Logic......Page 36 2.2 The Binary Decoder......Page 46 2.3 More on Gates: Reversible Gates......Page 50 2.4 Complete Sets of Operators......Page 55 2.5 Flip-Flops and Computer Memory......Page 58 2.6 Timing and Shift Registers......Page 62 3.1 Effective Procedures and Computability......Page 68 3.2 Finite State Machines......Page 71 3.3 The Limitations of Finite State Machines......Page 76 3.4 Turing Machines......Page 82 3.5 More on Turing Machines......Page 91 3.6 Universal Turing Machines and the Halting Problem......Page 96 3.7 Computability......Page 104 4. Coding and Information Theory......Page 110 4.2 Error Detecting and Correcting Codes......Page 111 4.3 Shannon's Theorem......Page 122 4.4 The Geometry of Message Space......Page 126 4.5 Data Compression and Information......Page 131 4.6 Information Theory......Page 136 4.7 Further Coding Techniques......Page 139 4.8 Analogue Signal Transmission......Page 145 5.1 The Physics of Information......Page 153 5.2 Reversible Computation and the Thermodynamics of Computing......Page 167 5.3 Computation: Energy Cost versus Speed......Page 183 5.4 The General Reversible Computer......Page 188 5.5 The Billiard Ball Computer......Page 192 5.6 Quantum Computation......Page 198 6.1 Introduction......Page 201 6.2 Computation with a Reversible Machine......Page 203 6.3 A Quantum Mechanical Computer......Page 207 6.4 Imperfections and Irreversible Free Energy Loss......Page 215 6.5 Simplifying the Implementation......Page 218 6.6 Conclusions......Page 226 6.7 References......Page 227 A Caveat from the Editors......Page 228 7.1 The Physics of Semiconductor Devices......Page 229 7.2 Energy Use and Heat Loss in Computers......Page 254 7.3 VLSI Circuit Construction......Page 273 7.4 Further Limitations on Machine Design......Page 290 Afterword: Memories of Richard Feynman......Page 300 Suggested Reading......Page 310 Index......Page 313 Title page 5 Contents 7 Foreword 10 Preface (Richard Feynman) 15 1. Introduction to Computers 17 1.1 The File Clerk Model 21 1.2 Instruction Sets 24 1.3 Summary 33 2. Computer Organization 36 2.1 Gates and Combinational Logic 36 2.2 The Binary Decoder 46 2.3 More on Gates: Reversible Gates 50 2.4 Complete Sets of Operators 55 2.5 Flip-Flops and Computer Memory 58 2.6 Timing and Shift Registers 62 3. The Theory of Computation 68 3.1 Effective Procedures and Computability 68 3.2 Finite State Machines 71 3.3 The Limitations of Finite State Machines 76 3.4 Turing Machines 82 3.5 More on Turing Machines 91 3.6 Universal Turing Machines and the Halting Problem 96 3.7 Computability 104 4. Coding and Information Theory 110 4.1 Computing and Communication Theory 111 4.2 Error Detecting and Correcting Codes 111 4.3 Shannon's Theorem 122 4.4 The Geometry of Message Space 126 4.5 Data Compression and Information 131 4.6 Information Theory 136 4.7 Further Coding Techniques 139 4.8 Analogue Signal Transmission 145 5. Reversible Computation and the Thermodynamics of Computing 153 5.1 The Physics of Information 153 5.2 Reversible Computation and the Thermodynamics of Computing 167 5.3 Computation: Energy Cost versus Speed 183 5.4 The General Reversible Computer 188 5.5 The Billiard Ball Computer 192 5.6 Quantum Computation 198 6. Quantum Mechanical Computers 201 6.1 Introduction 201 6.2 Computation with a Reversible Machine 203 6.3 A Quantum Mechanical Computer 207 6.4 Imperfections and Irreversible Free Energy Loss 215 6.5 Simplifying the Implementation 218 6.6 Conclusions 226 6.7 References 227 7. Physical Aspects of Computation 228 A Caveat from the Editors 228 7.1 The Physics of Semiconductor Devices 229 7.2 Energy Use and Heat Loss in Computers 254 7.3 VLSI Circuit Construction 273 7.4 Further Limitations on Machine Design 290 Afterword: Memories of Richard Feynman 300 Suggested Reading 310 Index 313 0201489910,9780201489910 From 1983 To 1986, The Legendary Physicist And Teacher Richard Feynman Gave A Course At Caltech Called Potentialities And Limitations Of Computing Machines. Although The Lectures Are Over Ten Years Old, Most Of The Material Is Timeless And Presents A Feynmanesque Overview Of Many Standard And Some Not-so-standard Topics In Computer Science. These Include Compatibility, Turing Machines (or As Feynman Said, Mr. Turing's Machines), Information Theory, Shannon's Theorem, Reversible Computation, The Thermodynamics Of Computation, The Quantum Limits To Computation, And The Physics Of Vlsi Devices. Taken Together, These Lectures Represent A Unique Exploration Of The Fundamental Limitations Of Digital Computers. Feynman's Philosophy Of Learning And Discovery Comes Through Strongly In These Lectures. He Constantly Points Out The Benefits Of Playing Around With Concepts And Working Out Solutions To Problems On Your Own - Before Looking At The Back Of The Book For The Answers. As Feynman Says In The Lectures: If You Keep Proving Stuff That Others Have Done, Getting Confidence, Increasing The Complexities Of Your Solutions - For The Fun Of It - Then One Day You'll Turn Around And Discover That Nobody Actually Did That One! And That's The Way To Become A Computer Scientist. Preface / Richard Feynman -- 1. Introduction To Computers -- 2. Computer Organization -- 3. The Theory Of Computation -- 4. Coding And Information Theory -- 5. Reversible Computation And The Thermodynamics Of Computing -- 6. Quantum Mechanical Computers -- 7. Physical Aspects Of Computation -- Afterword: Memories Of Richard Feynman. Richard P. Feynman ; Edited By Anthony J.g. Hey And Robin W. Allen. Includes Bibliographical References And Index. Covering the theory of computation, information and communications, the physical aspects of computation, and the physical limits of computers, this text is based on the notes taken by one of its editors, Tony Hey, on a lecture course on computation given by Richard Feynman.