Bitwise Page 7
Some time after I left Microsoft, I met one of the AOL engineers who’d worked against me during the interop war. We had a huge laugh over it. I complimented him on the genius of the buffer-overrun exploit, even as I bemoaned my loss. “It had been a great game,” I said. He agreed. We were both dumbstruck that we were still two of a very small number of people who knew the real story, after all these years.
The other lesson of the chat wars is that one cannot understand the technological or sociological impact of software without a solid grounding in code. That understanding has to begin from the bottom up, from the fundamental essence of code and computation: the binary bit.
* This process is called “dogfooding,” referring to a company that claimed its dogfood was so good its own employees ate it.
3
BINARIES
Praxis and Theory
Our ordinary habits make it easy to talk as though in saying “computing” we were dealing with something well delimited, an item of a sort….The matter is more subtle than that. Instead I consider computing to be a human activity involving certain human purposes and intents, certain human insights, and certain man-made tools and techniques.
—PETER NAUR
AT MICROSOFT, I dealt with buddy lists and chat sessions, but it didn’t matter to me who these people were or what they were saying. I cared only about shuttling notifications and delivering messages, like the postal service. Like the computers I programmed, I was disconnected from any human meaning of the data. There were only the generic forms of “people” and “messages.” Otherwise, the data was as opaque to me as it was to the servers. Both I and my programs were concerned with computation, not understanding.
Computers are first and foremost machines for doing calculations far more quickly and perfectly than humans. It’s even there in the name: the word “computation” historically referred to the reckoning of numbers. When Milton writes of the constellations’ “starry dance in numbers that compute / Days, months, and years,” he is describing the heavens’ computation of numerical time. Yet there’s very little in Logo, instant messenger, and the buffer overflow that appears to be mathematics. The computer is indeed doing math—simple math, for the most part. But computation isn’t arithmetic so much as the act of doing arithmetic, and the significance of computers’ work today is that the numbers they compute represent our reality. They represent it very crudely, and they do so with great trouble, but we use computers by making their numbers mean something to us.
The history of computers developed along two parallel paths. On the one hand, there is the engineering work of building better machines that do calculations. On the other, there is the theoretical work of exploring what those calculations can mean algorithmically and in our world. In the 1930s and 1940s, Alan Turing theorized different models of computation, while engineers like Konrad Zuse (who built what was arguably the first programmable computer, the Z3, in 1941) created increasingly general-purpose computing machines with scant knowledge of their theoretical possibilities and limitations. Computer science (the theory) and software engineering (the practice) influence each other bidirectionally, and both sides have been critical to the evolution of computers as we know them. Theoreticians gave us more sophisticated computer languages to program in. Theoreticians identified the artificial intelligence models that allowed for supervised training on datasets. But it was only when deployed on the huge datasets and clusters at Google that these models yielded revolutionary results, in areas such as image recognition and Go strategy. Many, including myself, were shocked when Google’s AlphaGo beat top human players at Go in 2016. The sheer combinatorial complexity of Go had me convinced that it would be another decade before a computer could take the top spot. The maxim known as Moore’s Law (after Intel co-founder Gordon Moore) states that the number of transistors that engineers are able to fit into an integrated circuit doubles approximately every two years. In other words, raw computational power increases exponentially. The top computers contained thousands of transistors in 1970; today they have billions. But computers are not necessarily millions of times smarter than they were then, and their achievements, like AlphaGo, can still come as surprises to us. Machine intelligence depends on computing power, but only loosely. It also depends on intellectual progress in computer science.
There are computer scientists who make a point to do as little programming as possible. There are many coders who have only a passing familiarity with the theory of computer science. As with most divides, each side would benefit from more familiarity with the other. Machine learning, in particular, has greatly profited from the close relationships between engineers and scientists, because the practical results of machine learning are often strong indicators of what approaches to pursue. Yet a theoretician’s eye is still needed to question machine learning paradigms and construct new approaches. I chose to become an engineer because I wanted to build things rather than prove them, but without the theoretical structure provided by my background in computer science, I wouldn’t have been half the engineer I was.
Computers today are a thick layer cake of abstractions. Many engineers work at one level while being only vaguely conscious of the other. The chip designer doesn’t think about web pages. The web designer knows little of silicon. But every serious software engineer understands how the layers fit together, and just as importantly, how they tend to recapitulate similar theoretical ideas of structure and purpose. And that knowledge then informs engineers’ design of new abstraction layers, making them better, more robust, and more elegant.
Movies and television present code as cryptic lines of arcane commands on a screen. This image is a mystifying ruse. A programmer should be able to look at good code and, with some effort, derive a fundamental simplicity to its organization and function—a set of organizing principles that structure the code in a neat and predictable way. This understanding arises from one’s knowledge of the hidden reality that lies behind all code. And that reality, in a word, is logic.
Truthtellers and Liars
All that logic warrants is a hope, and not a belief.
—CHARLES SANDERS PEIRCE
There is a type of puzzle, made most famous by the logician Raymond Smullyan (and by the movie Labyrinth), that involves liars and truthtellers. Suppose there are only two types of people, those who always tell the truth and those who always lie. Assuming that, can we determine who is the liar and who is the truthteller in this exchange?
MOLLY: Leopold is a liar.
LEOPOLD: We are both liars.
The reasoning goes that Leopold cannot be telling the truth, because if he is a truthteller, his statement is a lie, which would be a contradiction. So he must be a liar. Therefore, his statement is false and Leopold and Molly are not both liars. Since Leopold is a liar, Molly must be a truthteller. And sure enough, Molly’s statement is true.
Here’s a variant that I gave to my six-year-old daughter. There are two doors. Behind one is a huge amount of money. Behind the other is a shark. You don’t know which. There’s writing on the doors:
DOOR 1: The shark is in here!
DOOR 2: Both doors are lying.
Which door do you open? The logic is the same as with Molly and Leopold. Door 2 must be lying, because it’s impossible to truthfully say that you are a liar. So Door 1 must be true (or else Door 2 would be telling the truth), the shark is behind Door 1, and the money is behind Door 2.
I compulsively worked through hundreds of these sorts of logic puzzles as a kid. I’m fortunate my mother stumbled upon Smullyan’s Alice in Puzzle-Land, which became my introduction to the field of Boolean logic (the binary logic that underpins all computers), liar and truthteller puzzles, and logical paradoxes. Smullyan’s use of Lewis Carroll’s heroine aptly suited his truthteller puzzles, as the rigid yet arbitrary rules of logic matched up perfectly with th
e original Alice books. Carroll had been an expert logician himself.
After Alice, I located Smullyan’s other books, notably What Is the Name of This Book? and The Lady or the Tiger?, which presented similar puzzles in disparate settings like Transylvania and Renaissance Italy. His other books delved into Taoist and Zen-inflected parables but also discussed analytic philosophy, to which Smullyan had contributed as a logician.
Some of the puzzles in these books grew extraordinarily ornate, requiring multiple levels of inference. Sometimes I wasn’t told what one or another person had said. Sometimes “yes” and “no” were replaced with nonsense words that meant either “yes” or “no,” but I wasn’t told which. There were abstruse puzzles that attempted to explain Kurt Gödel’s incompleteness theorem—unsuccessfully, in my case.*1 But one puzzle genuinely irritated me. This is a simplified version:
A man is trying to figure out which of two caskets contains a portrait. “THE PORTRAIT IS NOT IN HERE” is written on the first casket. On the second casket: “EXACTLY ONE OF THESE CASKETS IS TELLING THE TRUTH.” Where’s the portrait? I went through the possibilities. Whether or not the second casket is telling the truth, the first casket must not be: either the second casket is true and the first casket is therefore false, or the second casket is false and thus the first casket must be false as well (or else the second casket would be telling the truth!). In the puzzle, the man also figures the portrait is in the first casket. He opens it up, and finds…nothing. The portrait is in the second casket. He’s utterly baffled. I was baffled too. The answer seemed indisputable.
Here is what Smullyan wrote as an explanation:
Without any information given about the truth or falsity of any of the sentences, nor any information given about the relation of their truth-values, the sentences could say anything, and the object could be anywhere. Good heavens, I can take any number of caskets that I please and put an object in one of them and then write any inscriptions at all on the lids; these sentences won’t convey any information.
I felt cheated. I felt that Smullyan had made an implicit promise that he would be providing logic problems that made sense! But, I grudgingly observed, the other puzzles explicitly claimed that the rules were being obeyed, and in this puzzle, there was no such guarantee. The lesson was that truth and falsity are not absolute, but relative to a context. Outside that context, statements lose sense and meaning. Without the guarantee that the rules are being followed, we can never be sure that our reasoning is valid. Nowhere is that more true than in the logical, and contextually isolated, world of computers.
1s and 0s
What is a man so made that he can understand number and what is number so made that a man can understand it?
—WARREN MCCULLOCH
The mark of the computer is the mark of the digital: everything is encoded in binary, 1s and 0s. The unit of the computer, and of data itself, is the bit, a single binary digit. All digital data, no matter what it appears to be, is at its heart grounded in its core representation in a language of two symbols, or alternatively, a language of one symbol (1) or the absence of a symbol (0). A language of exactly two possibilities.
On the surface, our world does not conform to this language of 1s and 0s. So computational operations, which are built on top of binary, appear alien. Plenty of things, however, can be represented on the computer, and therefore in binary: text, graphics, sounds, videos, programs. As the phenomena and their representations become more complex, some people argue that the digital translation is a corruption of the original.*2 The argument has been made against CDs, digital video, even digital watches. The “aura” of the flesh-and-blood original is lost, or some ineffable vital essence is corrupted and removed in the process. But this is not the case. What we think of as getting lost in the analog to digital translation is actually what is lost in any inexact translation from one form into another. A cassette dub of a vinyl record loses more than ripping a CD to a digital file.
Theoretically, anything can be represented in binary—a book, a piece of music, a cellular organism, a star system. In practice, however, we don’t yet have the capabilities to do this kind of digital specification for complex structures, so the human brain (about as complex as anything gets) will not become translatable into computable binary representations anytime soon. The process of representation does not necessarily seek perfection, but transparency, the point at which the digital replica becomes practically indistinguishable from the original phenomenon. Meteorologists use computer simulations to produce vastly more sophisticated weather models than existed a few decades ago, but weather is so chaotic that we only produce better educated guesses, not perfect ones. On the other hand, acoustic simulations have become so sophisticated that audio technology can reproduce room ambiences and echoes quite precisely, and synthesis of acoustic instruments becomes more sophisticated year by year. The digital recipe does not contain the aural experience of the music any more than a weather simulation creates rain, but a sufficiently precise recipe is what allows for the original phenomenon (music, cells, weather) to be re-created, given the right resources and tools. A computer screen can only show us an image of a painting, but were we to map every speck of paint in that painting, marking every variation in fabric and tone and color, and every daub and splatter, a sufficiently sophisticated machine could re-create the painting exactly—theoretically. In practice, computers and robots could become good enough to produce humanly indistinguishable copies, given sufficient technological advancement. All the information one needs to create the picture can be captured. But what is the essence of the original painting? Is it the physical object itself, or the data that describes it?
This is a trick question. The painting itself is the data, albeit in analog form rather than digital. By scanning it, we translate it into a different, less aesthetically pleasing recipe, yet one that contains the same information. “Things” themselves are already representations in one language or another. Everything is a representation of some underlying conception of ours. A film is represented in ink on a negative and in photons against a screen. Music is represented in the magnetic organization of oxide on a tape—or, more purely, in the series of waves that resonate against one’s eardrum. A chair is represented as a particular configuration of wood and metal; a physical book as patterns of ink on pages. We just tend not to think of these analog physical objects as representations (or recipes) of abstract concepts, but they too contain data. We tend to draw arbitrary distinctions between analog and digital encodings. These distinctions do not hold up. “Data” can come in any number of formats, not just the digital.
Distinctions between reality and the data that represents it are blurred, yet we cling to them. For example, Orthodox Jews are not permitted to erase or desecrate the written name of God. They avoid writing the name of God at all, and so avoid the need to store the papers in a synagogue or bury them in a cemetery.*3 In the late twentieth century, rabbis needed to assess the issue of writing the name of God on a computer screen. In 1998, Rabbi Moshe Saul Klein ruled that sacred names may be freely erased from a screen or disk. Klein’s assistant Yossef Hayad said:
The letters on a computer screen are an assemblage of pixels, dots of light, what have you. Even when you save it to disk, it’s not…anything more than a sequence of ones and zeroes.
Letters written on a page, however, are also an assemblage—of particles of ink. Other rabbinical analyses have made a distinction between “permanent” and “temporary” forms of writing, noting that the letters on a screen are erased and redrawn dozens of times per second. So the restriction, then, is on a “permanent” assemblage of some kind of “ink” in the physical shape of the name of God. Braille is permanent, for example. Even here there are ambiguities: What would the rabbis think of LED message board arrays? Dry-erase boards? Magnetic sketch boards? Scrabble tiles?
I don’t mean to
cause more trouble for rabbis. Rather, I want to point out the imprecision of the categorization. We think that objects in our world divide neatly into concrete or virtual, digital or analog, permanent or temporary, and the like. But there are cases that don’t quite fit into either category. Orthodox Jews often avoid typing the name of God on a computer to avoid the risk that someone might print out their page and inadvertently create a “permanent” hard copy. While the bit’s distinction between 0 and 1 is absolute, it’s rare for that distinction to hold up robustly in the complex phenomena of life. It holds up most of the time, but that’s not quite good enough, as we’ll see.
On and Off
Those who say mathematics is logic are not meaning by “logic” at all the same thing as those who define logic as the analysis and criticism of thought.
—FRANK RAMSEY
Computers did not force us into a new realm of the digital. Just because a particular phenomenon, whether it’s a CD or an email, is made of bits and bytes or 1s and 0s doesn’t mark the digital as a realm entirely different from the pre-digital. The digital was hidden in the analog world long before computers rolled around—in the formal logic of Smullyan’s truthteller puzzles, for example. The impact of computation lies not in 1s and 0s, but in a related but very different binary: true and false.
For a computer programmer, the two binaries of true/false and 1/0 quickly become interchangeable. True is 1 and false is 0.*4 Most computer languages make an explicit distinction between a Boolean variable (which can be true or false) and a numerical variable (which can be 1, 0, or some other number), but in practice this division blurs. This owes to the incredibly tight relationship between logic and mathematics in computation.