The Discrete Charm of the Machine: Why the World Became Digital

The Discrete Charm of the Machine

The

Discrete

Charm

of the

Machine

Why the World

Became Digital

Ken

Steiglitz

Princeton University Press / Princeton and Oxford

Copyright © 2019 by Princeton University Press

Published by Princeton University Press

41 William Street, Princeton, New Jersey 08540

In the United Kingdom: Princeton University Press

6 Oxford Street, Woodstock, Oxfordshire OX20 1TR

press.princeton.edu

All Rights Reserved

Library of Congress Control Number: 2018936381

ISBN 978-0-691-17943-8

eISBN 978-0-691-18417-3 (ebook)

Version 1.0

British Library Cataloging-in-Publication Data is available

Editorial: Vickie Kearn

Production Editorial: Leslie Grundfest

Text Design: Chris Ferrante

Production: Jacquie Poirier

Publicity: Sara Henning-Stout

Copyeditor: Jennifer McClain

To my daughter Bonnie

Contents

To the Reader  xiii

Part I / A Century of Valves  1

1    The Discrete Revolution  3

1.1    My Golden Age of Garbage  3

1.2    Nostalgia and the Aesthetics of Technology  4

1.3    Some Terminology  6

2    What’s Wrong with Analog?  10

2.1    Signals and Noise  10

2.2    Reproduction and Storage  11

2.3    The Origins of Noise  11

2.4    Thermal Noise in Electronics  12

2.5    Other Noise in Electronics  13

2.6    Digital Immunity  17

2.7    Analog Rot  19

2.8    Caveats  20

3    Signal Standardization  22

3.1    A Reminiscence  22

3.2    Ones and Zeros  22

3.3    Directivity of Control  24

3.4    Gates  24

3.5    The Electron  25

3.6    Edison’s Lightbulb Problems  26

3.7    De Forest’s Audion  27

3.8    The Vacuum Tube as Valve  30

3.9    The Rest of Logic  33

3.10   Clocks and Doorbells  34

3.11   Memory  35

3.12   Other Ways to Build Valves  36

4    Consequential Physics  43

4.1    When Physics Became Discrete  43

4.2    The Absolute Size of Things  46

4.3    The Heisenberg Uncertainty Principle  47

4.4    Explaining Wave-Particle Duality  49

4.5    The Pauli Exclusion Principle  50

4.6    Atomic Physics  53

4.7    Semiconductors  54

4.8    The P-N Junction  56

4.9    The Transistor  58

4.10  Quantum Tunneling  59

4.11   Speed  60

5    Your Computer Is a Photograph  62

5.1    Room at the Bottom  62

5.2    The Computer as Microphotograph  64

5.3    Heisenberg in the Chip Foundry  66

5.4    Moore’s Law and the Time of Silicon:ca. 1960–?  68

5.5    The Exponential Wall  74

Part II / Sound and Pictures  77

6    Music from Bits   79

6.1    The Monster in 1957  79

6.2    A Chance Encounter with a D-to-A Converter  81

6.3    Sampling and Monsieur Fourier  82

6.4    Nyquist’s Sampling Principle  83

6.5    Another Win for Digital  86

6.6    Another Isomorphism  88

7    Communication in a Noisy World  90

7.1    Claude Shannon’s 1948 Paper  90

7.2    Measuring Information  91

7.3    Entropy  94

7.4    Noisy Channels  96

7.5    Coding  97

7.6    The Noisy Coding Theorem  101

7.7    Another Win for Digital  102

Part III / Computation  105

8    Analog Computers  107

8.1    From the Ancient Greeks  107

8.2    More Ingenious Devices  111

8.3    Deeper Questions  117

8.4    Computing with Soap Films  119

8.5    Local and Global  121

8.6    Differential Equations  123

8.7    Integration  125

8.8    Lord Kelvin’s Research Program  126

8.9    The Electronic Analog Computer  129

9    Turing’s Machine  132

9.1    The Ingredients of a Turing Machine  132

9.2    The All-Analog Machine  133

9.3    The Partly Digital Computer  134

9.4    A Reminiscence: The Stored-Program Loom in New Jersey  135

9.5    Monsieur Jacquard’s Loom  136

9.6    Charles Babbage  138

9.7    Babbage’s Analytical Engine  141

9.8    Augusta Ada Byron, Countess of Lovelace  143

9.9    Turing’s Abstraction  144

10    Intrinsic Difficulty  148

10.1   Being Robust  148

10.2   The Polynomial/Exponential Dichotomy  149

10.3   Turing Equivalence  151

10.4   Two Important Problems  153

10.5   Problems with Easily Checked Certificates (NP)  154

10.6   Reducing One Problem to Another  156

10.7   Yes/No Problems  157

10.8   Cook’s Theorem: 3-SAT Is NP-Complete  158

10.9   Thousands More NP-Complete Problems  160

11    Searching for Magic  164

11.1    Analog Attacks on NP-Complete Problems  164

11.2    The Missing Law  169

11.3    The Church-Turing Thesis  170

11.4    The Extended Church-Turing Thesis  171

11.5    Locality: From Einstein to Bell  172

11.6    Behind the Quantum Curtain  176

11.7    Quantum Hacking  178

11.8    The Power of Quantum Computers  179

11.9    Life Itself  180

11.10  The Uncertain Limits of Computation  182

Part IV / Today and Tomorrow  183

12    The Internet, Then the Robots  185

12.1    Ideas  185

12.2    The Internet: Packets, Not Circuits  187

12.3    The Internet: Photons, Not Electrons  189

12.4    Enter Artificial Intelligence  193

12.5    Deep Learning  194

12.6    Obstacles  196

12.7    Enter Robots  202

12.8    The Problem of Consciousness  204

12.9    The Question of Values  206

Epilogue  209

Notes  211

Bibliography  221

Index  229

To the Reader

What this book is about

The machines we call computers have reshaped our lives, and may in the end transform humanity itself. The revolution is based on just one idea: build devices that store and manipulate information in the form of discrete bits. My aim in this book is to explain why this seemingly simple idea is so powerful.

It happens without trying that in pinpointing the virtues of the discrete, digital form, questions arise about the limits of the spectacular progress in technology we’ve seen in the past half century. Computers are cramming more and more components into smaller and smaller spaces, operating faster and faster. Can this go on forever? Computer programs are getting more and more clever. Are there problems that will always be beyond the reach of computers? Will computers become more clever than we? Will they replace us?

At the end of the book, we return to the opening theme and pose a further fundamental question: Will digital computers always be superior to analog computers, which use information in continuous, nondiscrete form, or is there some magic that remains hidden in the analog world, beyond the reach of the digital computer? The human brain uses both digital and analog forms of information—is Nature keeping some secrets to herself about the ultimate nature of computation?

Who is the intended reader?

Briefly: My ideal reader is interested in science generally, perhaps computers in particular, but is not technically trained. And she just might be curious about why computers are digital. This book is not by any means an introduction to computer science, nor is it about how to program or use computers. There are no equations and no computer code. The reader will not escape, however, without some knowledge of how today’s computers are built at the most basic, microscopic level, and an appreciation of why they got that way.

A quick tour

There are a number of reasons why computers are digital. Some are physical in nature, and these naturally tend to be more concrete and intuitively clear. For example, the inevitable presence of noise, everywhere in nature, tends to obscure information. Similarly, electrical current consists of the flow of discrete particles called electrons. This means that electrical signals are, at the microscopic level, necessarily granular. We begin, in part I, by discussing these physical obstacles to reliable computation and how they are circumvented by storing and using information in digital form.

We next show how the familiar notion of a valve can provide a building block for all computation. The transistor is a valve in silicon, and the explosive development of solid-state technology reflected in Moore’s law has given us the integrated circuit chip that today holds more than a billion transistors. We shall see that the limits of this progress will ultimately be determined by quantum mechanics and, in particular, by Heisenberg’s uncertainty principle.

Part II is devoted to two fundamental ideas that emerge from the study of communication rather than physics. Their development resulted in digital signal processing, high-speed networking, and the internet. The resulting ability to share sound and images almost instantly across the globe has changed our lives profoundly in just one generation.

The first idea, Fourier analysis, tells us that we can treat any signal as being composed of a collection of different frequencies. This insight leads to Nyquist’s principle, which determines just how fast we need to sample audio and video signals to preserve all their information, and is behind the concept of bandwidth, now a commonly recognized—and critical—resource in our modern world.

The second idea is the use of coding to protect information in a noisy environment. The empirical practice of using redundancy for safely transmitting and storing signals inspired an elegant and influential theory of information, which sprang fully fledged from the brain of Claude Shannon. The crown jewel of the theory is his remarkable (and surprising) noisy coding theorem, which reveals the full depth and significance of the concept of bandwidth.

In part III we move on to yet more sophisticated and challenging territory, ending up, in fact, at the limits of current scientific knowledge. Returning to analog machines for computation, we develop the notion of a problem that is intrinsically difficult. At this point we get a taste of modern complexity theory, the concept of an NP-complete problem, and the most important open problem in computer science.

Finally, we ask if there might be ways to escape the limits of the computers we use today. This leads naturally to the Church-Turing thesis, which asserts that the hypothetical machine invented by Alan Turing essentially captures the concept of computation; and the extended Church-Turing thesis, which takes this one step further, proposing that the Turing machine is the embodiment of all practical computation (including analog). We will see that neither thesis is purely mathematical in nature, and neither can ever be proved. From here it is a short step to questions about the ultimate power of computers that take advantage of quantum mechanics.

In the concluding chapter, which constitutes part IV, we review the six main ideas that, in barely a half century, transformed our information technology from analog to digital and led to today’s packet-switched and optically delivered internet. We arrive at the edge of the unknown: Are NP-complete problems intrinsically difficult? (Probably yes.) Do Turing machines capture the notion of all practical computation? (Probably yes, with a quantum-mechanical upgrade.) Can machines be conscious, and can they suffer? (Quite up in the air.) Whatever the answers to these questions, and regardless of whether their brains will be able to tap unknown analog or quantum power, the current accelerating development of discrete machines is attending the birth of autonomous robots. Ready or not, the robots are coming! How will we face our responsibility to our heirs and successors? Will our human cultural values survive?

A personal note

I grew up on masterpieces of popular science like Gamow (1947), Courant and Robbins (1996), and, later, Russell (2009) and Feynman (2006). These books share one essential feature: they simplify and at times may cut corners, but they never, ever lie. As Ralph Leighton says to the hypothetical student in his preface to Feynman (2006), There is nothing in this book that has to be ‘unlearned.’ With this book I have tried, with my limited resources and all the humility I can muster, to follow these heroes.

Finally, I must confess to a nostalgic attachment to the analog/digital theme. I was born at just about the same time that the first functioning digital computers were being built, but I grew up listening to remarkably practical analog radio. My first paycheck was for summer work writing assembler code for a vacuum-tube digital computer, but I used analog computers in some of my undergraduate courses. My dissertation was on the correspondence between analog and digital signal processing. Throughout this book-in-sonata-form, we develop the analog/digital theme from a variety of points of view; I invite you to chapter 1, the exposition section.

Acknowledgments

There is always the fear that acknowledging the aid or inspiration of colleagues and friends will implicate them in my mischief. Nevertheless, I thank the following for help of all sorts; they are appreciated and blameless: Andrew Appel, Sanjeev Arora, David August, György Buzsáki, Bernard Chazelle, David Dobkin, Mike Fredman, Jack Gelfand, Mike Honig, Andrea LaPaugh, Kai Li, Richard Lipton, Christos Papadimitriou, Mona Singh, Olga Troyanskaya, Kevin Wayne, Andy Yao.

For encouragement, expert guidance, and good cheer, I am also indebted to the staff at Princeton University Press, including acquisitions editor Vickie Kearn, production editor Leslie Grundfest, and editorial assistant Lauren Bucca, as well as to copyeditor Jennifer McClain.

Part I

A Century of Valves

1 The Discrete Revolution

1.1 My Golden Age of Garbage

What is usually called the computer revolution is really about much more—it’s about a radical conversion of our view of the world from continuous to discrete. As for your author, my entrance into this world couldn’t have been timed better to observe the apparently sudden transformation. I arrived in 1939, a few months before Hitler invaded Poland. At that time the stage had been set, rather subtly and gradually, for the development of things digital, and the pressure of the ensuing war years propelled us all, not so subtly and not so gradually, into what we now know as the Digital Age. This book is about the most basic ideas and principles behind the change. Why did the world change in such a fundamental way from analog to digital, and where might we humans—a species itself built along both analog and digital lines—be headed?

I apologize for the rather dark beginning, but it’s a fact that the dirty fingers of war have never failed to leave their prints on the annals of what we term progress. The dawn of the computer age is closely linked to decryption efforts in World War II, as well as to the development of the atomic bomb.

On August 6, 1945, I was only dimly aware of the fact that I was in New Jersey and not Japan, where bombardier Thomas Ferebee was watching Hiroshima’s Aioi Bridge in the crosshairs of his Norden bombsight. The bombsight, which subsequently released the first uranium-fission atomic bomb and began the end of World War II, was an analog computer. It solved the equations of motion that determined the path of the bomb, using things like cams and gears, a gyroscope, and a telescope, all mechanical devices. But it was a computer nevertheless, although applying the term to a mess of moving steel parts might surprise some people today. Well into the 1950s there were two kinds of computers: analog and digital. In fact, analog computers of the electronic sort were the only way to solve certain kinds of complicated problems, and were, in a handful of situations, very useful. Electronic analog computers were programmed by plugging wires into a patch panel, which was like a telephone switchboard (you may have seen one in an old movie), and by the time any interesting problem was running, the patch panel was a rat’s nest.

But before the mid-twentieth century everything was analog; digital just hadn’t been invented.¹ The most important piece of information technology I knew as a child was the radio, very analog at the time, and it was my remarkable piece of good fortune when the postwar engines of production turned to consumer goods, and consumers bought new, streamlined, plastic radios. Garbage night meant that the monstrous mahogany console radios of the 1930s could often be found curbside—with booming bass, hardly any treble because of the limitations of AM broadcasting, and all manner of interesting electronic parts inside.² That was how I learned to love the glow of vacuum tubes and the aroma of hot rosin-core solder congealing around the twisted leads of condensers (as capacitors were called), resistors, coils, and other more exotic components. Sometimes it was an autopsy that I performed on these found radios, but often it was a vivi-section, since many of them worked, or could be made to work, excellently. Some of these lucky finds even had shortwave bands, and garbage night turned out to be my gateway to the world at large.

It was all analog. When television came, that, too, was all analog. So were telephones. There just wasn’t anything else.

1.2 Nostalgia and the Aesthetics of Technology

Video and audio signals fly in and out of our brains all day long, and devices that process those signals—radio, television, recorded film and music players, telephones—were all digitized in the latter half of the twentieth century; that is, within my lifetime. One consequence is that the devices we use every day for what is now called digital signal processing have more or less converged to the same, rather dull-looking machine—essentially a small chip behind a screen, in a plastic case, occasionally with a couple of wires hanging out. In contrast, in the good old days radios were radios, television sets were television sets, cameras cameras, telephones telephones. You could tell what a device did by looking at it. And sometimes you would need an elephant to make it portable: the Stromberg Carlson console radio I lugged home with the help of my friends was crafted with a sturdy wooden cabinet, housing a loudspeaker with a huge electromagnet, a large lit dial, and hefty knobs that gave the operator the feeling of controlling an important piece of equipment—to a child, and perhaps to a grown-up as well, a spaceship.

My favorite effect was the magic eye tuning indicator, usually a 6E5 vacuum tube that had a fluorescent screen at its end, visible in a circular hole on the front panel of the radio. It glowed green with a dark crescent that contracted in proportion to the signal strength. Carefully tuning a station to reduce the crescent to a narrow slit was a joyful experience, especially in a dark room where the eerie glow did seem magical for sure. Punching in the frequency (or URL) of a radio station just does not provide the same tactile and visual pleasure. If your childhood came after such electronic apparatus, you don’t know what I’m talking about; such is the nature of nostalgia. No doubt the iPhone will stimulate similar feelings fifty years from now, when signals may very well go directly to our brains without the need for any beautiful little intermediary machines.

Of course there is a lively market for retro style and retro devices; certain cults have grown around the disappearance of, for example, shellac, vinyl, and analog tape recordings, or film cameras and the once pervasive technology of chemical-based photography. It’s common to hear that vacuum-tube amplifiers have a warmer sound, although it’s not certain how much of the warmth is due to distortion from the inherent nonlinearity of the vacuum-tube analog technology, or the psychological glow from the hot tubes themselves.

Sometimes the nostalgic longing approaches the mystical. Water Lily Acoustics produces superb recordings of Indian classical music, and they go through great pains to keep the sound recording free of the digital taint until the very last step in the process. For example, the booklet for a compact disc recording of Ustad Imrat Khan offers the following assurance:³

This is a pure analog recording done exclusively with custom-built vacuum-tube electronics. The microphone set-up was the classic Blumlein arrangement. No noise reduction, equalization, compression, or limiting of any sort was used in the making of this recording.

The booklet goes on to describe the microphones (which use tubes), recorder (Ampex MR70, half-inch, two-track, 15-inch-per-second tape, using vacuum tubes called nuvistors), and so on.

Spiritual values aside, a good analog sound recording, or, for that matter, a good analog photograph taken with film and printed well, can be, technically, a lot better than a bad digital recording or a bad digital photograph. We have much more to say about the ultimate and practical limitations of analog and digital technology as we go along.

1.3 Some Terminology

So far, we’ve been using the terms digital and analog rather loosely. Before going further, we need to clarify this terminology. For our purposes, digital means that a signal of interest is being represented by a sequence or array of numbers; analog means that a signal is represented by the value of some continuously variable quantity. This variable can be the voltage or current in an electrical circuit, say, or the brightness of a scene at some point, or temperature, pressure, velocity, and so on, as long as its value is continuously variable. All the possible values of a digital signal can be counted, and there is a definite gap between them; those of an analog variable cannot be counted, and there is no definite gap between them. Generally, we use discrete (actually discrete-valued) to mean digital and continuous (actually continuous-valued) to mean analog, although this overlooks some distinctions that are not important at this point.

When you buy a wristwatch or a clock, for example, you have a choice between an analog display and a digital display. This is exactly the sense in which we use the terms—but take note of the fact that we refer to the display and not the internal mechanism of the timekeeper. A clock with an analog display has hands that can move continuously, whereas a digital display shows numbers that change discontinuously, which is another way to say suddenly. The hands of a clock actually represent time by the rotational position of gears. These days, the usual clock with an analog display has an internal timekeeping mechanism that is digital (except for old-fashioned windup clocks). But at one point there were the opposite kinds of clocks, with analog mechanisms and digital displays—usually using gears and cams to flip displays with numbers printed on them.

On the morning of Pi Day (March 14) of 2015, there was a moment a bit after 9:26 and 53 seconds when the time could be written 3.14159265358979...; that is, π. The moment was fleeting to say the least; it was infinitesimally brief. And it will never occur again. Ever. If you were watching the hands of a clock with an analog display, you might have tried to take a photo at the exact moment of π, but the photo would have taken some finite time, and you would have necessarily blurred the second hand. That is an inevitable consequence of measuring an analog quantity of any kind.

Very commonly, audio and video signals are represented by voltages, either in a computer, smartphone, copper cable, or some kind of electrical circuit like those in an amplifier. This is the usual way that such signals are recorded by microphones and video cameras, and the resulting signals are transmitted and reproduced using voltages in electrical circuits. A microphone converts a sound pressure wave in the air to a time-varying voltage. A video camera converts a light image into an array of time-varying voltages. These audio and video signals usually start their lives out as analog signals and are converted to digital form after their initial capture, assuming that they are going to be processed in some way in digital form.

The device that converts an analog signal to digital form is called, naturally, an analog-to-digital converter (A-to-D converter), and the opposite operation is performed by a digital-to-analog converter (D-to-A converter). Thus, for example, the light-sensitive screen in a digital camera is really an A-to-D converter, whereas your computer monitor is really a D-to-A converter.

I’ll try to be clear about what I mean when we use the terms digital, analog, discrete, and continuous, but I should mention some possible sources of confusion. First, it often happens that it is time itself that is thought of as discrete or continuous, rather than the values of a signal. When there is any possible confusion, I will state explicitly that time is being considered. Second, there is the awkward fact that standard mathematical terminology uses the term continuous in a slightly different way. Mathematically speaking, a curve is continuous if it does not jump suddenly from one value to another but rather changes smoothly. The reader who has studied calculus will be aware of this alternate interpretation, but will not be confused by it.

Finally, the term discrete is used by physicists in another sense. A most important example of this usage comes up when we ask the question, What is light? The question has puzzled scientists for