Computer Science

  At the risk of boring some readers of The Berkeley Write, I've decided to review the remarkable history of computer science, from its barely existing a half century ago to being at the core of almost everything now.  That history is remarkable not merely because computers have become so ubiquitous, but especially because computer science has fundamentally changed the way we solve problems. 

  When I was an electrical engineering undergraduate at MIT in the late 1940s, I was dumbfounded to find that a classmate was studying Boolean algebra, an algebra of logic.  As one who was steeped in the mathematics of the continuum, I asked him why he was interested in an algebra having only two values—0 and 1.  He told me that he wanted to study digital computers. 

  I couldn't understand why he would be wasting his time.  Although I had worked on electro-mechanical analog computers during the summer after my freshman year, I scarcely knew what a digital computer was, and had absolutely no inkling at all of the revolution they would shortly ignite.  In my own exculpation, I should say that there were only a handful of them in existence at the time, and that even Thomas Watson, founder and then-chairman of IBM, had a few years earlier estimated their ultimate world-wide commercial market to be about five.  (To paraphrase John Kenneth Galbraith's remark about economic forecasting: The only function of engineering forecasting is to make astrology look respectable.)

  In 1960, when I joined the faculty at UC Berkeley, digital computers were much more widespread, but the term "computer science" was still an oxymoron: few could perceive any science there at all.  The study of computers at Cal, as elsewhere, was embedded in the department of electrical engineering, where the few courses on computers involved only the design of their electronic circuitry, peripherals and elementary programming.  Later in the decade, a few faculty members started going beyond those engineering issues, into basic research on the limits on digital computation and the theory of programming languages—i.e., computer science.

  Computer science has since come a very long way, now equally sharing with mathematics the role of fundament of all the sciences, and being central to many non-science disciplines as well.  Most particularly, it has largely changed our way of solving problems, from classical analysis to algorithmic procedures.

  In mathematics and the sciences, classical analysis is characterized by theorem proving and by the formulation of problems so that they can be solved by equations.  You had doses of that way of thinking in your high school geometry, algebra and physics courses, if not further.  For example, you encountered the quadratic equation, y = ax² + bx + c (often arising in the physics of motion), and were asked to find the values of x for which y = 0.   The two solutions of that problem turned out to be x = - (b/2a) ± ((b² – 4ac)^1/2)/2a.  That's pure analysis.

  On the other hand, algorithmic thinking is characterized by a step-by-step, iterative procedure, the modus operandi of computers.  The process for such thinking is often described by a flow chart such as that below, which is taken from one of the forms of the federal income tax return.  You start at the box at the upper left, and step through the chart by answering a series of yes/no questions.  If you get to the box labeled "You must figure your penalty," you then proceed to a set of forms that, rather than giving a formula for calculation of the penalty, guides you through a sequence of "if-then" statements to make the calculation, one step at a time.  That's a pure algorithmic procedure.

  Computer science now occupies a central role in the physical sciences and elsewhere because many problems are too complex for mathematical analysis—for example, the behavior of chaotic systems such as the weather or population dynamics, or of economic systems with a large numbers of variables and participants. To investigate such a problem, a sophisticated algorithmic procedure is designed to model the system at hand, and the procedure is then run on a computer to provide insight into the system's performance.  It's not just a matter of using the computer as a glorified calculator; to get accurate results in reasonable amounts of time and formats, investigators must be as steeped in the fundamentals of computer science as their predecessors were in mathematics.

  Even though computer science didn't start flourishing until the 1960s, it had its ur-moment in 1935 in England in the work of Alan Turing.  He posited a machine that manipulates symbols in a step-by-step fashion.  The device, now called a Turing machine, is quintessentially algorithmic.  Turing never built one.  His genius consisted in specifying an iterative procedure that even now models any computer program and therefore any computer.

  Turing, a superbly talented mathematician, also used the concept of his machine to address a question his contemporary Kurt Gödel had tackled: the completeness of mathematics. Gödel's Incompleteness Theorem showed that some true mathematical statements can't be mathematically proved to be true.  Turing approached the question differently, from the viewpoint of the computability of algorithms.  In a result very much related to Gödel's theorem, he showed that not all problems are solvable computationally in a finite amount of time.

  The question of computability is now front and center in computer science.  Even if a problem is theoretically computable in a finite amount of time, the time needed may be unreasonably large, given the exabyte (quintillion byte) data sets that are becoming common in such scientific and commercial operations as the Large Hadron Collider, the Sloan Digital Sky Survey, the World Data Centre for Climate, Amazon, YouTube, Google, etc.  (The first of these generates a quadrillion bytes of data—more than the information in all the world's libraries—every second!)  This "big data" challenge goes to the heart of computer science: how to effectively organize huge data sets, and how to formulate algorithms that handle them both efficiently in computation time and accurately as the size of the data set increases. 

  An indication of the current importance of big data is the establishment this year of a major research institute at UC Berkeley with a private $60-million grant from the Simons Foundation.  The institute will bring together researchers from around the world to study efficient algorithmic approaches to such important big-data subjects as evolution, the immune system, maintaining privacy while doing data analysis, and climate modeling. You will surely hear much more about big-data research in the next decade.

  So, to repeat: in my own professional lifetime, computer science has come from barely existing at all to being "at the core of almost everything," even of disciplines that were not previously thought of as particularly quantitative.  I find it a stunning story.

Gödel and God

    Kurt Gödel, whom some have called the greatest logician since Aristotle, undermined the very foundations of classical mathematics with his Incompleteness Theorem (and, by the way, thereby reaffirmed his belief in God).  To mathematicians, his work was nothing short of cataclysmic.  To most of the rest us, it is merely counter-intuitive, paradoxical and maddening.  I invite you down the rabbit hole into a realm of paradox worthy of Alice.

  Until Gödel proved his theorem, it was thought that mathematics—alone of the sciences—was self-contained, not having to refer to anything outside mathematics.  Mathematics was created by mathematicians as a complete, fenced-off entity, while other scientists had to discover the outside world.  More precisely, mathematicians held that any true statement in any properly set up mathematical system (say arithmetic or algebra) could be shown to be true by using solely the axioms and rules of that system.

  Gödel proved the opposite.  His theorem shows that any properly set up mathematical system containing arithmetic has true statements within it that cannot be proved true by using solely the axioms and rules of that system.  Mathematics is therefore not complete unto itself as was supposed.  Confirmation of the truths not provable within mathematics can only be found outside of what had previously been assumed to be a self-contained mathematics.  This is where God came in for Gödel—but more about that later.

  It all started at the turn of the twentieth century, when Bertrand Russell realized that mathematical logic would always contain contradictions.  He illustrated this by using a folksy paradox about a lone, male barber in a town where every male keeps himself clean-shaven either by shaving himself or being shaved by the barber.  Then, Russell asked, who shaves the barber?  There's the paradox: If the barber doesn't shave himself then he (the barber) must shave himself; if the barber shaves himself, then he (the barber) doesn't shave himself.

  Such paradoxes are called self-referential.  In this one, all males must refer themselves to the barber if they don't shave themselves.  The barber, being male, must thus refer himself to himself to be shaved if he doesn't shave himself, setting up the paradox. 

  The proof of Gödel's Incompleteness Theorem is very complicated, but its core consists of the construction of a true, self-referential arithmetical proposition that is shown to be unprovable within arithmetic.  A taste of the core argument can be found in a much simpler argument about a supposedly self-contained truth-telling machine:

1. Imagine a truth-telling machine M that can answer all questions allowing solely a yes or no answer about the truth of any statement submitted to it, but by axiom can only answer correctly; that is, it cannot lie.  (M stands in the stead of Gödel's starting point of arithmetic.)

2.  Consider the statement S, that “M will never say S is true.”  (This is akin to the self-referential proposition in arithmetic that Gödel constructed, for the statement S is defined in terms of the statement S.)

3.  Ask M if S is true.

4.  If M says S is true, then "M will never say S is true" is thereby falsified, so M has incorrectly answered a question.  Hence, M cannot say that S is true, since by axiom it gives only correct answers.

5. Step 4 confirms that M will never say S is true, verifying that the statement S in step 2 is indeed true.

6.  Here’s the dilemma:  S is true but M cannot say so.  M is consequently an incomplete truth-telling machine.  The answer to "Is S true?" lies outside of M. 

  Gödel's theorem, which rocked the world of mathematics, didn't shock Gödel.  He had been a lifelong Platonist, believing with Plato that anything we can see or conceive of is just a poor shadow of an eternal, objective ideal that exists beyond the real world.  It was hence no surprise to him that there are mathematical truths that mathematics cannot prove.  He concluded that proofs of those truths are part of the omniscience of an eternal God who is external to the real world, thus strengthening his long-held theism.  In his later years, Gödel even tried to construct a formal logical proof of God's existence.

  Gödel published his theorem in 1931, when he was just 25.  He fled the Nazis from his native Austria in 1938, and spent his last forty years at the Institute for Advanced Study in Princeton, where he became Albert Einstein's closest intellectual companion until Einstein's death in 1955. 

  As I suggested at the outset, understanding paradoxes like those I've described can be maddening—perhaps just reading this blog posting has had that effect on you.  Worse, they might quite literally drive mad those whose life work involves them, and perhaps that's what happened to Gödel.  In a great irony, Gödel died in 1978 in a self-referential sort of way, so convinced that people were trying to poison him that he refused to eat and died of starvation.

  If you want to read more about Gödel—the man, his life, his times, and details about his theorem and its proof—I recommend Incompleteness: The Proof and Paradox of Kurt Gödel by Rebecca Goldstein.