Feynman Lectures on Computation

✍ Scribed by Richard P. Feynman

• Publisher: Addison-Wesley
• Year: 1996
• Tongue: English
• Leaves: 318
• Category: Library

✦ Synopsis

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.”

✦ Table of Contents

Cover......Page 1
Title page......Page 4
Contents......Page 6
Foreword......Page 9
Preface (Richard Feynman)......Page 14
1. Introduction to Computers......Page 16
1.1 The File Clerk Model......Page 20
1.2 Instruction Sets......Page 23
1.3 Summary......Page 32
2.1 Gates and Combinational Logic......Page 35
2.2 The Binary Decoder......Page 45
2.3 More on Gates: Reversible Gates......Page 49
2.4 Complete Sets of Operators......Page 54
2.5 Flip-Flops and Computer Memory......Page 57
2.6 Timing and Shift Registers......Page 61
3.1 Effective Procedures and Computability......Page 67
3.2 Finite State Machines......Page 70
3.3 The Limitations of Finite State Machines......Page 75
3.4 Turing Machines......Page 81
3.5 More on Turing Machines......Page 90
3.6 Universal Turing Machines and the Halting Problem......Page 95
3.7 Computability......Page 103
4. Coding and Information Theory......Page 109
4.2 Error Detecting and Correcting Codes......Page 110
4.3 Shannon's Theorem......Page 121
4.4 The Geometry of Message Space......Page 125
4.5 Data Compression and Information......Page 130
4.6 Information Theory......Page 135
4.7 Further Coding Techniques......Page 138
4.8 Analogue Signal Transmission......Page 144
5.1 The Physics of Information......Page 152
5.2 Reversible Computation and the Thermodynamics of Computing......Page 166
5.3 Computation: Energy Cost versus Speed......Page 182
5.4 The General Reversible Computer......Page 187
5.5 The Billiard Ball Computer......Page 191
5.6 Quantum Computation......Page 197
6.1 Introduction......Page 200
6.2 Computation with a Reversible Machine......Page 202
6.3 A Quantum Mechanical Computer......Page 206
6.4 Imperfections and Irreversible Free Energy Loss......Page 214
6.5 Simplifying the Implementation......Page 217
6.6 Conclusions......Page 225
6.7 References......Page 226
A Caveat from the Editors......Page 227
7.1 The Physics of Semiconductor Devices......Page 228
7.2 Energy Use and Heat Loss in Computers......Page 253
7.3 VLSI Circuit Construction......Page 272
7.4 Further Limitations on Machine Design......Page 289
Afterword: Memories of Richard Feynman......Page 299
Suggested Reading......Page 309
Index......Page 312