Ken Steiglitz: It’s the Number of Zeroes that Counts

We present the third installment in a series by The Discrete Charm of the Machine author Ken Steiglitz. You can find the first post here and the second, here.

 

The scales of space and time in our universe; in everyday life we hang out very near the center of this picture: 1 meter and 1 second.

As we’ll see in The Discrete Charm the computer world is full of very big and very small numbers. For example, if your smartphone’s memory has a capacity of 32 GBytes, it means it can hold 32 billion bytes, or 32000000000 bytes. It’s awfully inconvenient and error-prone to count this many zeros, and it can get much worse, so scientists, who are used to dealing with very large and small numbers, just count the number of zeros. In this case the memory capacity is 3.2×1010 bytes. At the other extreme, pulses in an electronic circuit might occur at the rate of a billion per second, so the time between pulses is a billionth of a second, 0.000000001, a nanosecond, 1 × 10−9 seconds. In the time-honored scientific lingo, a factor of 10 is an “order of magnitude,” and back-of-the-envelope estimates often ignore factors of 2 or 3. What’s a factor of 2 or 3 between friends? What matters is the number of zeroes. In the last example, a nanosecond is 9 orders of magnitude smaller than a second.

Such big and small numbers also come up in discussing the size of transistors, the number of them that fit on a chip, the speed of communication on the internet in bits per second, and so on. The figure shows the range of magnitudes we’re ever likely to encounter when we discuss the sizes of things and the time that things take. At the low extremes I indicate the size of an electron and the time between the crests of gamma-ray waves, just about the highest frequency we ever encounter. The electron is about 6 orders of magnitude smaller than a typical virus (and a single transistor on a chip); the frequency of gamma rays is about 10 orders of magnitude faster than a gigahertz computer chip.

To this computer scientist a machine like an automobile is pretty boring. It runs only one program, or maybe two if you count forward and reverse gear. With few exceptions it has four wheels, one engine, one steering wheel—and all cars go about as fast as any other, if they can move in traffic at all. I could take my father’s 1941 Plymouth out for a spin today and hardly anyone would notice. It cost about $845 in 1941 (for a four-door sedan), or about $14,000 in today’s dollars. In other words, in our order-of-magnitude world, it is a product that is practically frozen in time. On the other hand, my obsolete and clumsy laptop beats the first computer I ever used by 5 orders of magnitude in speed and memory, and 4 orders of magnitude in weight and volume. If you want to talk money, I remember paying about 50¢ a byte for extra memory for a small laboratory computer in 1971—8 orders of magnitude more expensive than today, or maybe 9 if you take inflation into account.

The number of zeros is roughly the logarithm (base-10), and plots like the figure are said to have logarithmic scales. You can see them in the chapter on Moore’s law in The Discrete Charm, where I need them to get a manageable picture of just how much progress has been made in computer technology over the last few decades. The shrinkage in size and speedup has been, in fact, exponential with the years—which means constant-size hops in the figure, year by year. Anything less than exponential growth would slow to a crawl. This distinction between exponential and slower-than-exponential growth also plays a crucial role in studying the efficiency of computer algorithms, a favorite pursuit of theoretical computer scientists and a subject I take up towards the end of the book.

Counting zeroes lets us to fit the whole universe on a page.

SteiglitzKen Steiglitz is professor emeritus of computer science and senior scholar at Princeton University. His books include The Discrete Charm of the MachineCombinatorial OptimizationA Digital Signal Processing Primer, and Snipers, Shills, and Sharks. He lives in Princeton, New Jersey.

Ken Steiglitz: Garage Rock and the Unknowable

Here is the second post in a series by The Discrete Charm of the Machine author Ken Steiglitz. You can access the first post here

I sat down to draft The Discrete Charm of the Machine with the goal of explaining, without math, how we arrived at today’s digital world. It is a quasi-chronological story; I take what I need, when I need it, from the space of ideas. I start at the simplest point, describing why noise is a constant threat to information and how using discrete values (usually zeros and ones) affords protection and a permanence not possible with information in analog (continuous) form. From there I sketch the important ideas of digital signal processing (for sound and pictures), coding theory (for nearly error-free communication), complexity theory (for computation), and so on—a fine arc, I think, from the boomy and very analog console radios of my childhood to my elegant little internet radio.

Yet the path through the book is not quite so breezy and trouble-free. In the final three chapters we encounter three mysteries, each progressively more fundamental and thorny. I hope your curiosity and sense of wonder will be piqued; there are ample references to further reading. Here are the problems in a nutshell:

  1. Is it no harder to find a solution to a problem than to merely check a solution? (Does P = NP?) This question comes up in studying the relative difficulty of solving problems with a computing machine. It is a mathematical question, and is still unresolved after almost 40 years of attack by computer scientists.
    As I discuss in the book, there are plenty of reasons to believe that P is not equal to NP and most computer scientists come down on that side. But … no one knows for sure.
  2. Are the digital computers we use today as powerful—in a practical sense—as any we can build in this universe (the extended Church-Turing thesis)? This is a physics question, and for that reason is fundamentally different from the P=NP question. Its answer depends on how the universe works.
    The thesis is intimately tied to the problem of building machines that are essentially more powerful than today’s digital computers—the human brain is one popular candidate. The question runs deep: some believe there is magic to found beyond the world of zeros and ones.
  3. Can a machine be conscious? Philosopher David Chalmers calls this the hard problem, and considers it “the biggest mystery.” It is not a question of mathematics, nor of physics, but of philosophy and cognitive science.

I want to emphasize that this is not merely the modern equivalent of asking how many angels could dance on the point of a pin. The answer has most serious consequences for us humans: it determines how we should treat our android creations, the inevitable products of our present rush to artificial intelligence. If machines are capable of suffering we have a moral responsibility to treat them compassionately.

My first reaction to the third question is that it is unanswerable. How can we know about the subjective mental life of anyone (or any thing) but ourselves? Philosopher Owen Flanagan called those who take this position mysterians, after the proto-punk band ? and the Mysterians. Michael Shermer joins this camp in his Scientific American column of July 1, 2018. I discuss the difficulty in the final chapter and remain agnostic—although I am hard-pressed even to imagine what form an answer would take.

I suggest, however, a pragmatic way around the big third question: Rather than risk harm, give the machines the benefit of the doubt. It is after all what we do for our fellow humans.

SteiglitzKen Steiglitz is professor emeritus of computer science and senior scholar at Princeton University. His books include The Discrete Charm of the MachineCombinatorial OptimizationA Digital Signal Processing Primer, and Snipers, Shills, and Sharks. He lives in Princeton, New Jersey.

 

Ken Steiglitz: When Caruso’s Voice Became Immortal

We’re excited to introduce a new series from Ken Steiglitz, computer science professor at Princeton University and author of The Discrete Charm of the Machine, out now. 

The first record to sell a million copies was Enrico Caruso’s 1904 recording of “Vesti la giubba.” There was nothing digital, or even electrical about it; it was a strictly mechanical affair. In those days musicians would huddle around a horn which collected their sound waves, and that energy was coupled mechanically to a diaphragm and then to a needle that traced the waveforms on a wax or metal-foil cylinder or disc. For many years even the playback was completely mechanical, with a spring-wound motor and a reverse acoustical system that sent the waveform from what was often a 78 rpm shellac disc to a needle, diaphragm, and horn. Caruso almost single-handedly started a cultural revolution as the first recording star and became a household name—and millionaire (in 1904 dollars)—in the process. All without the benefit of electricity, and certainly purely analog from start to finish. Digital sound recording for the masses was 80 years in the future.

Enrico Caruso drew this self portrait on April 11, 1902 to commemorate his first recordings for RCA Victor. The process was completely analog and mechanical. As you can see, Caruso sang into a horn; there were no microphones. [Public domain, from Wikimedia Commons]

The 1904 Caruso recording I mentioned is perhaps the most famous single side ever made and is readily available online. It was a sensation and music lovers who could afford it were happy to invest in the 78 rpm (or simply “78”) disc, not to mention the elaborate contraption that played it. In the early twentieth century a 78 cost about a dollar or so, but 1904 dollars were worth about 30 of today’s dollars, a steep price for 2 minutes and 28 seconds of sound full of hisses, pops, and crackles, and practically no bass or treble. In fact the disc surface noise in the versions you’re likely to hear today has been cleaned up and the sound quality greatly improved—by digital processing of course. But being able to hear Caruso in your living room was the sensation of the new century.The poor sound quality of early recordings was not the worst of it. That could be fixed, and eventually it was. The long-playing stereo record (now usually called just “vinyl”) made the 1960s and 70s the golden age of high fidelity, and the audiophile was born. I especially remember, for example, the remarkable sound of the Mercury Living Presence and Deutsche Grammophon labels. The market for high-quality home equipment boomed, and it was easy to spend thousands of dollars on the latest high-tech gear. But all was not well. The pressure of the stylus, usually diamond, on the vinyl disc wore both. There is about a half mile of groove on an LP record, and the stylus that tracks it has a very sharp, very hard tip; records wear out. Not as quickly as the shellac discs of the 20s and 30s, but they wear out.

The noise problem for analog recordings is exacerbated when many tracks are combined, a standard practice in studio work in the recording industry. Sound in analog form is just inherently fragile; its quality deteriorates every time it is copied or played back on a turntable or past a tape head.

Everything changed in 1982 with the introduction of the compact disc (CD), which was digital. Each CD holds about 400 million samples of a 74-minute stereo sound waveform, each sample represented by a 2-byte number (a byte is 8 bits). In this world those 800 million bytes, or 6.4 billion bits (zeros or ones) can be stored and copied forever, absolutely perfectly. Those 6.4 billion bits are quite safe for as long as our civilization endures.

There are 19th century tenors whose voices we will never hear. But Caruso, Corelli, Domingo, Pavarotti… their digital voices are truly immortal.

SteiglitzKen Steiglitz is professor emeritus of computer science and senior scholar at Princeton University. His books include The Discrete Charm of the MachineCombinatorial OptimizationA Digital Signal Processing Primer, and Snipers, Shills, and Sharks. He lives in Princeton, New Jersey.

Ken Steiglitz on The Discrete Charm of the Machine

SteiglitzA few short decades ago, we were informed by the smooth signals of analog television and radio; we communicated using our analog telephones; and we even computed with analog computers. Today our world is digital, built with zeros and ones. Why did this revolution occur? The Discrete Charm of the Machine explains, in an engaging and accessible manner, the varied physical and logical reasons behind this radical transformation. Ken Steiglitz examines why our information technology, the lifeblood of our civilization, became digital, and challenges us to think about where its future trajectory may lead.

What is the aim of the book?

The subtitle: To explain why the world became digital. Barely two generations ago our information machines—radio, TV, computers, telephones, phonographs, cameras—were analog. Information was represented by smoothly varying waves. Today all these devices are digital. Information is represented by bits, zeros and ones. We trace the reasons for this radical change, some based on fundamental physical principles, others on ideas from communication theory and computer science. At the end we arrive at the present age of the internet, dominated by digital communication, and finally greet the arrival of androids—the logical end of our current pursuit of artificial intelligence. 

What role did war play in this transformation?

Sadly, World War II was a major impetus to many of the developments leading to the digital world, mainly because of the need for better methods for decrypting intercepted secret messages and more powerful computation for building the atomic bomb. The following Cold War just increased the pressure. Business applications of computers and then, of course, the personal computer opened the floodgates for the machines that are today never far from our fingertips.

How did you come to study this subject?

I lived it. As an electrical engineering undergraduate I used both analog and digital computers. My first summer job was programming one of the few digital computers in Manhattan at the time, the IBM 704. In graduate school I wrote my dissertation on the relationship between analog and digital signal processing and my research for the next twenty years or so concentrated on digital signal processing: using computers to process sound and images in digital form.

What physical theory played—and continues to play—a key role in the revolution?

Quantum mechanics, without a doubt. The theory explains the essential nature of noise, which is the natural enemy of analog information; it makes possible the shrinkage and speedup of our electronics (Moore’s law); and it introduces the possibility of an entirely new kind of computer, the quantum computer, which can transcend the power of today’s conventional machines. Quantum mechanics shows that many aspects of the world are essentially discrete in nature, and the change from the classical physics of the nineteenth century to the quantum mechanics of the twentieth is mirrored in the development of our digital information machines.

What mathematical theory plays a key role in understanding the limitations of computers?

Complexity theory and the idea of an intractable problem, as developed by computer scientists. This theme is explored in Part III, first in terms of analog computers, then using Alan Turing’s abstraction of digital computation, which we now call the Turing machine. This leads to the formulation of the most important open question of computer science, does P equal NP? If P equals NP it would mean that any problem where solutions can just be checked fast can be solved fast. This seems like asking a lot and, in fact, most computer scientists believe that P does not equal NP. Problems as hard as any in NP are called NP-complete. The point is that NP-complete problems, like the famous traveling problem, seem to be intrinsically difficult, and cracking any one of them cracks them all.  Their essential difficulty manifests itself, mysteriously, in many different ways in the analog and digital worlds, suggesting, perhaps, that there is an underlying physical law at work. 

What important open question about physics (not mathematics) speaks to the relative power of digital and analog computers?

The extended Church-Turing thesis states that any reasonable computer can be simulated efficiently by a Turing machine. Informally, it means that no computer, even if analog, is more powerful (in an appropriately defined way) than the bare-boned, step-by-step, one-tape Turing machine. The question is open, but many computer scientists believe it to be true. This line of reasoning leads to an important conclusion: if the extended Church-Turing thesis is true, and if P is not equal to NP (which is widely believed), then the digital computer is all we need—Nature is not hiding any computational magic in the analog world.

What does all this have to do with artificial intelligence (AI)?

The brain uses information in both analog and digital form, and some have even suggested that it uses quantum computing. So, the argument goes, perhaps the brain has some special powers that cannot be captured by ordinary computers.

What does philosopher David Chalmers call the hard problem?

We finally reach—in the last chapter—the question of whether the androids we are building will ultimately be conscious. Chalmers calls this the hard problem, and some, including myself, think it unanswerable. An affirmative answer would have real and important consequences, despite the seemingly esoteric nature of the question. If machines can be conscious, and presumably also capable of suffering, then we have a moral responsibility to protect them, and—to put it in human terms—bring them up right. I propose that we must give the coming androids the benefit of the doubt; we owe them the same loving care that we as parents bestow on our biological offspring.

Where do we go from here?

A funny thing happens on the way from chapter 1 to 12. I begin with the modest plan of describing, in the simplest way I can, the ideas behind the analog-to-digital revolution.  We visit along the way some surprising tourist spots: the Antikythera mechanism, a 2000-year old analog computer built by the ancient Greeks; Jacquard’s embroidery machine with its breakthrough stored program; Ada Lovelace’s program for Babbage’s hypothetical computer, predating Alan Turing by a century; and B. F. Skinner’s pigeons trained in the manner of AI to be living smart bombs. We arrive at a collection of deep conjectures about the way the universe works and some challenging moral questions.

Ken Steiglitz is professor emeritus of computer science and senior scholar at Princeton University. His books include Combinatorial OptimizationA Digital Signal Processing Primer, and Snipers, Shills, and Sharks (Princeton). He lives in Princeton, New Jersey.

Browse our 2019 Computer Science Catalog

Our new Computer Science catalog includes an introduction to computational complexity theory and its connections and interactions with mathematics; a book about the genesis of the digital idea and why it transformed civilization; and an intuitive approach to the mathematical foundation of computer science.

If you’re attending the Information Theory and Applications workshop in San Diego this week, you can stop by the PUP table to check out our computer science titles!

 

Mathematics and Computation provides a broad, conceptual overview of computational complexity theory—the mathematical study of efficient computation. Avi Wigderson illustrates the immense breadth of the field, its beauty and richness, and its diverse and growing interactions with other areas of mathematics. With important practical applications to computer science and industry, computational complexity theory has evolved into a highly interdisciplinary field that has shaped and will further shape science, technology, and society. 

 

Steiglitz Discrete Charm of the Machine book cover

A few short decades ago, we were informed by the smooth signals of analog television and radio; we communicated using our analog telephones; and we even computed with analog computers. Today our world is digital, built with zeros and ones. Why did this revolution occur? The Discrete Charm of the Machine explains, in an engaging and accessible manner, the varied physical and logical reasons behind this radical transformation, and challenges us to think about where its future trajectory may lead.

Lewis Zax Essential Discrete Mathematics for Computer Science

Discrete mathematics is the basis of much of computer science, from algorithms and automata theory to combinatorics and graph theory. This textbook covers the discrete mathematics that every computer science student needs to learn. Guiding students quickly through thirty-one short chapters that discuss one major topic each, Essential Discrete Mathematics for Computer Science can be tailored to fit the syllabi for a variety of courses. Fully illustrated in color, it aims to teach mathematical reasoning as well as concepts and skills by stressing the art of proof.

Browse our 2018 Computer Science & Information Science Catalog

Our new Computer Science & Information Science catalog includes an accessible and rigorous textbook for introducing undergraduates to computer science theory, a fascinating account of the breakthrough ideas that transformed probability and statistics, and an amazing tour of many of history’s greatest unsolved ciphers.

If you’re attending the ITA Workshop-Information Theory and Its Application conference this week, please stop by our table to browse our full range of titles.

What Can Be Computed? is a uniquely accessible yet rigorous introduction to the most profound ideas at the heart of computer science. Crafted specifically for undergraduates who are studying the subject for the first time, and requiring minimal prerequisites, the book focuses on the essential fundamentals of computer science theory and features a practical approach that uses real computer programs (Python and Java) and encourages active experimentation. It is also ideal for self-study and reference.

Throughout, the book recasts traditional computer science concepts by considering how computer programs are used to solve real problems. Standard theorems are stated and proven with full mathematical rigor, but motivation and understanding are enhanced by considering concrete implementations. The book’s examples and other content allow readers to view demonstrations of–and to experiment with—a wide selection of the topics it covers. The result is an ideal text for an introduction to the theory of computation.

In the sixteenth and seventeenth centuries, gamblers and mathematicians transformed the idea of chance from a mystery into the discipline of probability, setting the stage for a series of breakthroughs that enabled or transformed innumerable fields, from gambling, mathematics, statistics, economics, and finance to physics and computer science. This book tells the story of ten great ideas about chance and the thinkers who developed them, tracing the philosophical implications of these ideas as well as their mathematical impact.

Complete with a brief probability refresher, Ten Great Ideas about Chance is certain to be a hit with anyone who wants to understand the secrets of probability and how they were discovered.

Unsolved! begins by explaining the basics of cryptology, and then explores the history behind an array of unsolved ciphers. It looks at ancient ciphers, ciphers created by artists and composers, ciphers left by killers and victims, Cold War ciphers, and many others. Some are infamous, like the ciphers in the Zodiac letters, while others were created purely as intellectual challenges by figures such as Nobel Prize–winning physicist Richard P. Feynman. Bauer lays out the evidence surrounding each cipher, describes the efforts of geniuses and eccentrics—in some cases both—to decipher it, and invites readers to try their hand at puzzles that have stymied so many others.

Geoff Mulgan on Big Mind: How Collective Intelligence Can Change Our World

A new field of collective intelligence has emerged in the last few years, prompted by a wave of digital technologies that make it possible for organizations and societies to think at large scale. This “bigger mind”—human and machine capabilities working together—has the potential to solve the great challenges of our time. So why do smart technologies not automatically lead to smart results? Gathering insights from diverse fields, including philosophy, computer science, and biology, Big Mind reveals how collective intelligence can guide corporations, governments, universities, and societies to make the most of human brains and digital technologies. Highlighting differences between environments that stimulate intelligence and those that blunt it, Geoff Mulgan shows how human and machine intelligence could solve challenges in business, climate change, democracy, and public health. Read on to learn more about the ideas in Big Mind.

So what is collective intelligence?

My interest is in how thought happens at a large scale, involving many people and often many machines. Over the last few years many experiments have shown how thousands of people can collaborate online analyzing data or solving problems, and there’s been an explosion of new technologies to sense, analyze and predict. My focus is on how we use these new kinds of collective intelligence to solve problems like climate change or disease—and what risks we need to avoid. My claim is that every organization can work more successfully if it taps into a bigger mind—mobilizing more brains and computers to help it.

How is it different from artificial intelligence?

Artificial intelligence is going through another boom, embedded in everyday things like mobile phones and achieving remarkable break throughs in medicine or games. But for most things that really matter we need human intelligence as well as AI, and an over reliance on algorithms can have horrible effects, whether in financial markets or in politics.

What’s the problem?

The problem is that although there’s huge investment in artificial intelligence there’s been little progress in how intelligently our most important systems work—democracy and politics, business and the economy. You can see this in the most everyday aspect of collective intelligence—how we organize meetings, which ignores almost everything that’s known about how to make meetings effective.

What solutions do you recommend?

I show how you can make sense of the collective intelligence of the organizations you’re in—whether universities or businesses—and how to become better. Much of this is about how we organize our information commons. I also show the importance of countering the many enemies of collective intelligence—distortions, lies, gaming and trolls.

Is this new?

Many of the examples I look at are quite old—like the emergence of an international community of scientists in the 17th and 18th centuries, the Oxford English Dictionary which mobilized tens of thousands of volunteers in the 19th century, or NASA’s Apollo program which at its height employed over half a million people in more than 20,000 organizations. But the tools at our disposal are radically different—and more powerful than ever before.

Who do you hope will read the book?

I’m biased but think this is the most fascinating topic in the world today—how to think our way out of the many crises and pressures that surround us. But I hope it’s of particular interest to anyone involved in running organizations or trying to work on big problems.

Are you optimistic?

It’s easy to be depressed by the many examples of collective stupidity around us. But my instinct is to be optimistic that we’ll figure out how to make the smart machines we’ve created serve us well and that we could on the cusp of a dramatic enhancement of our shared intelligence. That’s a pretty exciting prospect, and much too important to be left in the hands of the geeks alone.

MulganGeoff Mulgan is chief executive of Nesta, the UK’s National Endowment for Science, Technology and the Arts, and a senior visiting scholar at Harvard University’s Ash Center. He was the founder of the think tank Demos and director of the Prime Minister’s Strategy Unit and head of policy under Tony Blair. His books include The Locust and the Bee.

Matthew J. Salganik on Bit by Bit: Social Research in the Digital Age

In just the past several years, we have witnessed the birth and rapid spread of social media, mobile phones, and numerous other digital marvels. In addition to changing how we live, these tools enable us to collect and process data about human behavior on a scale never before imaginable, offering entirely new approaches to core questions about social behavior. Bit by Bit is the key to unlocking these powerful methods—a landmark book that will fundamentally change how the next generation of social scientists and data scientists explores the world around us. Matthew Salganik has provided an invaluable resource for social scientists who want to harness the research potential of big data and a must-read for data scientists interested in applying the lessons of social science to tomorrow’s technologies. Read on to learn more about the ideas in Bit by Bit.

Your book begins with a story about something that happened to you in graduate school. Can you talk a bit about that? How did that lead to the book?

That’s right. My dissertation research was about fads, something that social scientists have been studying for about as long as there have been social scientists. But because I happened to be in the right place at the right time, I had access to an incredibly powerful tool that my predecessors didn’t: the Internet. For my dissertation, rather than doing an experiment in a laboratory on campus—as many of my predecessors might have—we built a website where people could listen to and download new music. This website allowed us to run an experiment that just wasn’t possible in the past. In my book, I talk more about the scientific findings from that experiment, but while it was happening there was a specific moment that changed me and that directly led to this book. One morning, when I came into my basement office, I discovered that overnight about 100 people from Brazil had participated in my experiment. To me, this was completely shocking. At that time, I had friends running traditional lab experiments, and I knew how hard they had to work to have even 10 people participate. However, with my online experiment, 100 people participated while I was sleeping. Doing your research while you are sleeping might sound too good to be true, but it isn’t. Changes in technology—specifically the transition from the analog age to the digital age—mean that we can now collect and analyze social data in new ways. Bit by Bit is about doing social research in these new ways.

Who is this book for?

This book is for social scientists who want to do more data science, data scientists who want to do more social science, and anyone interested in the hybrid of these two fields. I spend time with both social scientists and data scientists, and this book is my attempt to bring the ideas from the communities together in a way that avoids the jargon of either community.  

In your talks, I’ve heard that you compare data science to a urinal.  What’s that about?

Well, I compare data science to a very specific, very special urinal: Fountain by the great French artist Marcel Duchamp. To create Fountain, Duchamp had a flash of creativity where he took something that was created for one purpose—going to the bathroom—and turned it a piece of art. But most artists don’t work that way. For example, Michelangelo, didn’t repurpose. When he wanted to create a statue of David, he didn’t look for a piece of marble that kind of looked like David: he spent three years laboring to create his masterpiece. David is not a readymade; it is a custommade.

These two styles—readymades and custommades—roughly map onto styles that can be employed for social research in the digital age. My book has examples of data scientists cleverly repurposing big data sources that were originally created by companies and governments. In other examples, however, social scientists start with a specific question and then used the tools of the digital age to create the data needed to answer that question. When done well, both of these styles can be incredibly powerful. Therefore, I expect that social research in the digital age will involve both readymades and custommades; it will involve both Duchamps and Michelangelos.

Bit by Bit devotes a lot attention to ethics.  Why?

The book provides many of examples of how researchers can use the capabilities of the digital age to conduct exciting and important research. But, in my experience, researchers who wish to take advantage of these new opportunities will confront difficult ethical decisions. In the digital age, researchers—often in collaboration with companies and governments—have increasing power over the lives of participants. By power, I mean the ability to do things to people without their consent or even awareness. For example, researchers can now observe the behavior of millions of people, and researchers can also enroll millions of people in massive experiments. As the power of researchers is increasing, there has not been an equivalent increase in clarity about how that power should be used. In fact, researchers must decide how to exercise their power based on inconsistent and overlapping rules, laws, and norms. This combination of powerful capabilities and vague guidelines can force even well-meaning researchers to grapple with difficult decisions. In the book, I try to provide principles that can help researchers—whether they are in universities, governments, or companies—balance these issues and move forward in a responsible way.

Your book went through an unusual Open Review process in addition to peer review. Tell me about that.

That’s right. This book is about social research in the digital age, so I also wanted to publish it in a digital age way. As soon as I submitted the book manuscript for peer review, I also posted it online for an Open Review during which anyone in the world could read it and annotate it. During this Open Review process dozens of people left hundreds of annotations, and I combined these annotations with the feedback from peer review to produce a final manuscript. I was really happy with the annotations that I received, and they really helped me improve the book.

The Open Review process also allowed us to collect valuable data. Just as the New York Times is tracking which stories get read and for how long, we could see which parts of the book were being read, how people arrived to the book, and which parts of the book were causing people to stop reading.

Finally, the Open Review process helped us get the ideas in the book in front of the largest possible audience. During Open Review, we had readers from all over the world, and we even had a few course adoptions. Also, in addition to posting the manuscript in English, we machine translated it into more than 100 languages, and we saw that these other languages increased our traffic by about 20%.

Was putting your book through Open Review scary?

No, it was exhilarating. Our back-end analytics allowed me see that people from around the world were reading it, and I loved the feedback that I received. Of course, I didn’t agree with all the annotations, but they were offered in a helpful spirit, and, as I said, many of them really improved the book.

Actually, the thing that is really scary to me is putting out a physical book that can’t be changed anymore. I wanted to get as much feedback as possible before the really scary thing happened.

And now you’ve made it easy for other authors to put their manuscripts through Open Review?

Absolutely. With a grant from the Sloan Foundation, we’ve released the Open Review Toolkit. It is open source software that enables authors and publishers to convert book manuscripts into a website that can be used for Open Review. And, as I said, during Open Review, you can receive valuable feedback to help improve your manuscript, feedback that is very complimentary to the feedback from peer review. During Open Review, you can also collect valuable data to help launch your book. Furthermore, all of these good things are happening at the same time that you are increasing access to scientific research, which is a core value of many authors and academic publishers.

SalganikMatthew J. Salganik is professor of sociology at Princeton University, where he is also affiliated with the Center for Information Technology Policy and the Center for Statistics and Machine Learning. His research has been funded by Microsoft, Facebook, and Google, and has been featured on NPR and in such publications as the New Yorker, the New York Times, and the Wall Street Journal.

Craig Bauer: Attacking the Zodiac Killer

While writing Unsolved! The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies, it soon became clear to me that I’d never finish if I kept stopping to try to solve the ciphers I was covering. It was hard to resist, but I simply couldn’t afford to spend months hammering away at each of the ciphers. There were simply too many of them. If I was to have any chance of meeting my deadline, I had to content myself with merely making suggestions as to how attacks could be carried out. My hope was that the book’s readers would be inspired to actually make the attacks. However, the situation changed dramatically when the book was done.

I was approached by the production company Karga Seven Pictures to join a team tasked with hunting the still unidentified serial killer who called himself the Zodiac. In the late 1960s and early 70s, the Zodiac killed at least five people and terrorized entire cities in southern California with threatening letters mailed to area newspapers. Some of these letters included unsolved ciphers. I made speculations about these ciphers in my book, but made no serious attempt at cracking them. With the book behind me, and its deadline no longer a problem, would I like to join a code team to see if we could find solutions where all others had failed? The team would be working closely with a pair of crack detectives, Sal LaBarbera and Ken Mains, so that any leads that developed could be investigated immediately. Was I willing to take on the challenge of a very cold case? Whatever the result was, it would be no secret, for our efforts would be aired as a History channel mini-series. Was I up for it? Short answer: Hell yeah!

The final code team included two researchers I had corresponded with when working on my book, Kevin Knight (University of Southern California, Information Sciences Institute) and David Oranchak (software developer and creator of Zodiac Killer Ciphers. The other members were Ryan Garlick (University of North Texas, Computer Science) and Sujith Ravi (Google software engineer).

My lips are sealed as to what happened (why ruin the suspense?), but the show premieres Tuesday November 14, 2017 at 10pm EST. It’s titled “The Hunt for the Zodiac Killer.” All I’ll say for now is that it was a rollercoaster ride. For those of you who would like to see how the story began for me, Princeton University Press is making the chapter of my book on the Zodiac killer freely available for the duration of the mini-series. It provides an excellent background for those who wish to follow the TV team’s progress.

If you find yourself inspired by the show, you can turn to other chapters of the book for more unsolved “killer ciphers,” as well challenges arising from nonviolent contexts. It was always my hope that readers would resolve some of these mysteries and I’m more confident than ever that it can be done!

BauerCraig P. Bauer is professor of mathematics at York College of Pennsylvania. He is editor in chief of the journal Cryptologia, has served as a scholar in residence at the NSA’s Center for Cryptologic History, and is the author of Secret History: The Story of Cryptology. He lives in York, Pennsylvania.

Global Math Week: Around the World from Unsolved to Solved

by Craig Bauer

BauerWhat hope do we have of solving ciphers that go back decades, centuries, or even all the way back to the ancient world? Well, we have a lot more hope than we did in the days before the Internet. Today’s mathematicians form a global community that poses a much greater threat to unsolved problems, of every imaginable sort, than they have every faced before.

In my Princeton University Press book, Unsolved! The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies, I collected scores of the most intriguing unsolved ciphers. It’s a big book, in proper proportion to its title, and I believe many of the ciphers in it will fall to the onslaught the book welcomes from the world’s codebreakers, both professionals and amateurs. Why am I making this prediction with such confidence? Well, I gave a few lectures based on material from the book, while I was still writing it, and the results bode well for the ciphers falling.

Here’s what happened.

Early in the writing process, I was invited to give a lecture on unsolved ciphers at the United States Naval Academy. I was surprised, when I got there, by the presence of a video camera. I was asked if I was okay with the lecture being filmed and placed on YouTube. I said yes, but inside I was cursing myself for not having gotten a much needed haircut before the talk. Oh well. Despite my rough appearance, the lecture went well.[1] I surveyed some of the unsolved ciphers that I was aware of at the time, including one that had been put forth by a German colleague and friend of mine, Klaus Schmeh. It was a double transposition cipher that he had created himself to show how difficult it is to solve such ciphers. He had placed it in a book he had written on unsolved ciphers, a book which is unfortunately only available in German.[2] But to make the cipher as accessible as possible, he assured everyone that that particular bit of writing was in English.

 

VESINTNVONMWSFEWNOEALWRNRNCFITEEICRHCODEEA

HEACAEOHMYTONTDFIFMDANGTDRVAONRRTORMTDHE

OUALTHNFHHWHLESLIIAOETOUTOSCDNRITYEELSOANGP

VSHLRMUGTNUITASETNENASNNANRTTRHGUODAAARAO

EGHEESAODWIDEHUNNTFMUSISCDLEDTRNARTMOOIREEY

EIMINFELORWETDANEUTHEEEENENTHEOOEAUEAEAHUHI

CNCGDTUROUTNAEYLOEINRDHEENMEIAHREEDOLNNIRAR

PNVEAHEOAATGEFITWMYSOTHTHAANIUPTADLRSRSDNOT

GEOSRLAAAURPEETARMFEHIREAQEEOILSEHERAHAOTNT

RDEDRSDOOEGAEFPUOBENADRNLEIAFRHSASHSNAMRLT

UNNTPHIOERNESRHAMHIGTAETOHSENGFTRUANIPARTAOR

SIHOOAEUTRMERETIDALSDIRUAIEFHRHADRESEDNDOION

ITDRSTIEIRHARARRSETOIHOKETHRSRUAODTSCTTAFSTHCA

HTSYAOLONDNDWORIWHLENTHHMHTLCVROSTXVDRESDR

Figure 1. Klaus Schmeh’s double transposition cipher challenge.

When the YouTube video went online, it was seen by an Israeli computer scientist, George Lasry, who became obsessed with it. He was not employed at the time, so he was able to devote a massive amount of time to seeking the solution to this cipher. As is natural for George, he attacked it with computer programs of his own design. He eventually found himself doing almost nothing other than working on the cipher. His persistence paid off and he found himself reading the solution.

I ended up being among the very first to see George’s solution, not because I’m the one who introduced him to the challenge via the YouTube video, but because I’m the editor-in-chief of the international journal (it’s owned by the British company Taylor and Francis) Cryptologia. This journal covers everything having to do with codes and ciphers, from cutting edge cryptosystems and attacks on them, to history, pedagogy, and more. Most of the papers that appear in it are written by men and women who live somewhere other than America and it was to this journal that George submitted a paper describing how he obtained his solution to Klaus’s challenge.

George’s solution looked great to me, but I sent it to Klaus to review, just to be sure. As expected, he was impressed by the paper and I queued it up to see print. The solution generated some media attention for George, which led to him being noticed by people at Google (an American company, of course). They approached him and, after he cleared the interviewing hurdles, offered him a position, which he accepted. I was very happy that George found the solution, but of course that left me with one less unsolved cipher to write about in my forthcoming book. Not a problem. As it turns out there are far more intriguing unsolved ciphers than can be fit in a single volume. One less won’t make any difference.

Later on, but still before the book saw print, I delivered a similar lecture at the Charlotte International Cryptologic Symposium held in Charlotte, North Carolina. This time, unlike at the Naval Academy, Klaus Schmeh was in the audience.

One of the ciphers that I shared was fairly new to me. I had not spoken about it publicly prior to this event. It appeared on a tombstone in Ohio and seemed to be a Masonic cipher. It didn’t look to be sophisticated, but it was very short and shorter ciphers are harder to break. Brent Morris, a 33rd degree Mason with whom I had discussed it, thought that it might be a listing of initials of offices, such as PM, PHP, PIM (Past Master, Past High Priest, Past Illustrious Master), that the deceased had held. This cipher was new to Klaus and he made note of it and later blogged about it. Some of his followers collaborated in an attempt to solve it and succeeded. Because I hadn’t even devoted a full page to this cipher in my book, I left it in as a challenge for readers, but also added a link to the solution for those who want to see the solution right away.

Bauer

Figure 2. A once mysterious tombstone just south of Metamora, Ohio.

So, what was my role in all of this? Getting the ball rolling, that’s all. The work was done by Germans and an Israeli, but America and England benefited as well, as Google gained yet another highly intelligent and creative employee and a British owned journal received another great paper.

I look forward to hearing from other people from around the globe, as they dive into the challenges I’ve brought forth. The puzzles of the past don’t stand a chance against the globally networked geniuses of today!

Craig P. Bauer is professor of mathematics at York College of Pennsylvania. He is editor in chief of the journal Cryptologia, has served as a scholar in residence at the NSA’s Center for Cryptologic History, and is the author of Unsolved!: The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies. He lives in York, Pennsylvania.

 

[1] It was split into two parts for the YouTube channel. You can see them at https://www.youtube.com/watch?v=qe0JhEajfj8 (Part 1) and https://www.youtube.com/watch?v=5L12gjgMOMw (Part 2). A few years later, I got cleaned up and delivered an updated version of the talk at the International Spy Museum. That talk, aimed at a wider audience, may be seen at https://www.youtube.com/watch?v=rsdUDdkjdQg.

[2] Schmeh, Klaus, Nicht zu Knacken, Carl Hanser Verlag, Munich, 2012.

Craig Bauer on unsolved ciphers

In 1953, a man was found dead from cyanide poisoning near the Philadelphia airport with a picture of a Nazi aircraft in his wallet. Taped to his abdomen was an enciphered message. In 1912, a book dealer named Wilfrid Voynich came into possession of an illuminated cipher manuscript once belonging to Emperor Rudolf II, who was obsessed with alchemy and the occult. Wartime codebreakers tried—and failed—to unlock the book’s secrets, and it remains an enigma to this day. In Unsolved, Craig Bauer examines these and other vexing ciphers yet to be cracked. Recently he took the time to answer some questions about his new book.

Why focus on unsolved ciphers?

They’re much more intriguing because they could be concealing anything. Some might reveal the identities of serial killers. Others could unmask spies, rewrite history, expose secret societies, or even give the location of buried treasure worth millions. This sense of mystery is very appealing to me.

Did you try to solve the ciphers yourself first?

There are so many unsolved ciphers that I realized I would never finish writing about them if I kept stopping to try to solve them. There’s one that I’m confident I could solve, but instead of doing so, I simply presented the approach I think will work and am leaving it for a reader to pursue. I expect that several of them will be solved by readers and I look forward to seeing their results!

Does someone who wants to attack these mysteries need to know a lot of mathematics or have computer programming skills?

No. Many of the ciphers were created by people with very little knowledge in either area. Also, past solvers of important ciphers have included amateurs. One of the Zodiac killer’s ciphers was solved by a high school history teacher. Some of the ciphers might be solved in a manner that completely bypasses mathematics. A reader may find a solution through papers the cipher’s creator left behind, perhaps in some library’s archives, in government storage, or in a relative’s possession. I think some may be solved by pursuing a paper trail or some other non-mathematical avenue. Of course, there are mathematical challenges as well, for those who have the skills to take them on. The puzzles span thousands of years, from ancient Egypt to today’s online community. Twentieth century challenges come from people as diverse as Richard Feynman (a world-class physicist) and Ricky McCormick (thought to have been illiterate).

Are all of the unsolved ciphers covered in the book?

No, far from it. There are enough unsolved ciphers to fill many volumes. I limited myself to only the most interesting examples, and still there were too many! I originally set out to write a book about half the size of what was ultimately published. The problem was that there was so much fascinating material that I had to go to 600 pages or experience the agony of omitting something fabulous. Also, unsolved ciphers from various eras are constantly coming to light, and new ones are created every year. I will likely return to the topic with a sequel covering the best of these.

Which cipher is your favorite?

I’m the most excited about the Paul Rubin case. It involves a cipher found taped to the abdomen of a teenage whiz-kid who was found dead in a ditch by the Philadelphia airport, way back in 1953. While I like well-known unsolved ciphers like the Voynich Manuscript and Kryptos, I have higher hopes for this one being solved because it hasn’t attracted any attention since the 1950s. The codebreakers have made a lot of progress since then, so it’s time to take another look and see what can be learned about this young man’s death. I felt it was very important to include cases that will be new even to those who have read a great deal about cryptology already and this is one such case.

Should the potential reader have some prior knowledge of the subject?

If he or she does, there will still be much that is new, but for those with no previous exposure to cryptology, everything is explained from the ground up. As a teenager I loved books at the popular level on a wide range of topics. In particular, the nonfiction of Isaac Asimov instilled in me a love for many subjects. He always started at the beginning, assuming his readers were smart, but new to the topic he was covering. This is the approach that I have taken. I hope that the book finds a wide readership among the young and inspires them in the same way Asimov inspired me.

Is there anything that especially qualifies you to write on this topic?

Early work on this book was supported by the National Security Agency through their Scholar-in-Residence program at the Center for Cryptologic History. They wanted me in this role because, while I have a PhD in mathematics and have carried out mathematical research in cryptology, I also have a passion for history and other disciplines. In fact, both of my books have the word “history” in their titles. The journal Cryptologia, for which I serve as the editor-in-chief, is devoted to all aspects of cryptology, mathematical, historical, pedagogical, etc. My love of diverse fields allows me to write with enthusiasm about ciphers in music, art, criminal cases, ancient history, and other areas. The broad approach to the subject is more entertaining and ensures that there’s something in the book for nearly every reader.

BauerCraig Bauer is professor of mathematics at York College of Pennsylvania. He is editor in chief of the journal Cryptologia, has served as a scholar in residence at the NSA’s Center for Cryptologic History, and is the author of Unsolved! The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies. He lives in York, Pennsylvania.

Craig Bauer: The Ongoing Mystery of Unsolved Ciphers (and new hope)

When a civilization first develops writing and few people are literate, simply putting a message down on paper can be all that is required to keep an enemy from understanding it. As literacy spreads, a more sophisticated method is needed, which is why codes and ciphers, a.k.a. “secret writing,” always follow closely on the heels of the discovery of writing. Over the millennia, ciphers have become extremely sophisticated, but so too have the techniques used by those attempting to break them.

In recent decades, everyone from mathematicians and computer scientists to artists and authors have created ciphers as challenges to specialists or the general public, to see if anyone is clever enough to unravel the secrets. Some, like the first three parts of James Sanborn’s sculpture Kryptos and the ciphers appearing in the television show Gravity Falls, have been solved, while others remain mysteries. The highly secretive online society known as Cicada 3301 has repeatedly issued such challenges as a means of talent scouting, though for what purpose such talented individuals are sought remains unknown. One unsolved cipher was laid down as a challenge by former British army intelligence officer Alexander d’Agapeyeff in his book Codes & Ciphers (1939). Sadly, when frustrated letters of enquiry reached the author, he admitted that he had forgotten how to solve it! Another was made by the famous composer Edward Elgar in 1897 as a riddle for a young lady friend of his. She, along with various experts, all failed to ferret out the meaning and Elgar himself refused to reveal it.

 

Elgar's cipher

Elgar’s cipher

 

Many unsolved ciphers appear in much more serious contexts. The serial killer who referred to himself as “The Zodiac” was responsible for at least five murders, as well as the creation of several ciphers sent to San Francisco newspapers. While the first of these ciphers was solved, others remain unbroken. Could a solution to one of these lead to an identification of the killer? Although many have speculated on his identity, it has never been firmly established. The Zodiac is not the only murderer to have left us such mysterious communiques, he is just the best known. Other killers’ secrets have persisted through relative obscurity. How many readers have heard of Henry Debsonys? In 1883, a jury sentenced him to death for the murder of his wife, after deliberating for only nine minutes. But this unfortunate woman was Henry’s third wife and the first two died under strange circumstances. Had Henry killed all of them? Will the ciphers he left behind confirm this? I think his ciphers will be among the first to fall this year, thanks to a major clue I provide in my book, Unsolved: The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies. There are many more such criminal ciphers. One deranged individual even sent threatening letters containing ciphers to John Walsh of America’s Most Wanted fame! The FBI’s codebreakers maintain a list of their top unsolved ciphers. At present, only two of these are known to the public, but many others that didn’t make the top 10 are available for anyone to try to crack.

How do codebreakers, whether amateur or professional, meet the challenges they face? Statistics and other areas of mathematics often help, as do computers, but two of the codebreakers’ most powerful tools are context and intuition. This is why ciphers have often been broken by amateurs with no programming skills and little knowledge of mathematics. Enter Donald Harden, a high school history teacher, who with assistance from his wife Bettye, broke one of the Zodiac killer’s ciphers by guessing that the egotistical killer’s message would begin with “I” and contain the word “KILL.” Context allows the attacker to guess words, sometimes entire phrases, that might appear in the message. These are known as cribs. During World War II, the German word eins (meaning one) appeared in so many Nazi messages that a process known as “einsing” was developed, searching the cipher for the appearance of this word in every possible position. In today’s ciphers, the word President appears frequently.

Of course, time and again cribs and intuition can lead in the wrong direction. Indeed, the single most important attribute for a codebreaker is patience. A good codebreaker will have the ability to work on a cipher for months, for that is sometimes what it takes to reach a solution, ignoring the body’s normal demands for food and sleep; during World War I, the French codebreaker Georges Painvin lost 33 pounds over three months while sitting at a desk breaking the German ADFGX and ADFGVX ciphers.

Fig 2

Fig 3Is it possible that some of the earliest known ciphers, dating from the ancient world, have survived unread by anyone other than those they were created for? I believe this is the case and that they’ve been hiding in plain sight, like the purloined letter in Poe’s classic tale. Those studying ancient cultures have long been aware of so-called “nonsense inscriptions.” These appear on Egyptian sarcophagi, Greek vases, runestones, and elsewhere. They are typically dismissed as the work of illiterates imitating writing, merely because the experts cannot read them. But all of these cultures are known to have made use of ciphers and some of the contexts of the inscriptions are so solemn (e.g. sarcophagi) that it’s hard to believe they could be meaningless. I’d like to see a closer examination of these important objects. I expect some of the messages will be read in the near future, if cryptologists can form collaborations with linguists. These two groups have worked together successfully in military contexts for many decades. It is time that they also join forces for historical studies.

With a very large number of unsolved ciphers, spanning millennia, having been composed by a diverse group of individuals, it seems likely that it will take a diverse group of attackers, with skills ranging over many disciplines, to solve them. Some mysterious texts may reveal themselves to clever computer programmers or linguists, others to those taking the psychological approach, getting into the creator’s head and guessing phrases he or she used in the cipher, and some may be broken by readers who manage to discover related material in government archives or private hands that provides just enough extra information to make the break. I look forward to seeing the results!

BauerCraig P. Bauer is professor of mathematics at York College of Pennsylvania. He is editor in chief of the journal Cryptologia, has served as a scholar in residence at the NSA’s Center for Cryptologic History, and is the author of Unsolved!: The History and Mystery of the World’s Greatest Ciphers from Ancient Egypt to Online Secret Societies. He lives in York, Pennsylvania.