10002 Things
Every Self-Respecting Computer Scientist Should Know

David Evans
University of Richmond, 10 November 2003

Slides: http://www.cs.virginia.edu/evans/talks/richmond/richmond.ppt

What is Computer Science?

Computer science is the study of information processes. It is not a natural science since it deals primarily with unnatural, abstract stuff like numbers, graphs, strings and procedures. Rather, it is more like mathematics. The key difference between computer science and mathematics is that where mathematics is declarative (it deals with what is knowledge), computer science is imperative (it deals with how to knowledge). Computer science centers on understanding how to describe procedures (that is, precise methods for manipulating information) and to reason about the information processes they encode.

I do not know when I have been so tantalized by anything, and should be ashamed to say how much time I have spent upont it, in vain. These Functional Equations are complete Will-o-the-Wisps to me. The moment I fancy I have really at last got hold of something tangible and substantial, it all receded further and further and vanishes again into thin air...
Ada Byron, letter to Augustus De Morgan, 27 November 1841.
From Ada, the Enchantress of Numbers: A Selection from the Letters of Lord Byron's Daughter and Her Description of the First Computer, by Betty A. Toole, 1998.)

For more information: Ada Byron, CS200 Lecture 1

What problem did the first electronic programmable computer solve?

If you want to try and break a simple variant of the Lorenz Cipher, try CS200 Problem Set 4. If you are up for a bigger challenge, try breaking the Enigma variant on CS588 Problem Set 2.

Why was the first "personal computer" built?

  • Some Funny Things Happened on the Way to the Moon, Richard H. Battin, 1989.
  • One Giant Leap: The Apollo Guidance Computer, Dag Spicer, from Dr. Dobb's Journal. (Includes computer specs.)

    The MIT Instrumentation Lab had been designing software for the Apollo onboard guidance system even before the word software was invented. I still remember the first time I told my wife that I was in charge of "Apollo Software". She exhorted me: "Please don't tell any of our friends!"
    Some Funny Things Happened on the Way to the Moon, Richard H. Battin, 1989.

    • Is Computer Science a science, engineering or other?

    The Liberal Arts

    Trivium (Language)
       Grammar: study of meaning in written expression
       Rhetoric: comprehension of verbal and written discourse
       Logic: argumentative discourse for discovering truth

    Quandrivium (Number)
       Arithmetic: understanding numbers
       Geometry: quantification of space
       Music: number in time
       Astronomy: laws of the planets and stars
             Read Neil deGrasse Tyson's Science's Endless Golden Age

    What are the world's most complex programs?

    NCBI Human Genome Resources
    Swarm Computing

    What is and is not computable?

    Procedure: A precise description of a process.
    Alrogithm: A procedure that always terminates.

    A problem is decidable is there exists an algorithm that can solve the problem for all possible inputs. It is not necessary to know what that algorithm is to say a problem is decidable, only to know that some algorithm to solve it must exist. For example, chess is a decidable problem, even if we do not yet know an algorithm that solves it.

    A problem is undecidable is there is no algorithm that can solve the problem. There might be a procedure, but it is not guaranteed to terminate.

    We can prove the halting problem is undecidable informally by arguing that if we could define halts?, we could use it to define contradict-halts: 

    (define (contradict-halts)
  (if (halts? contradict-halts) 
      (infinite-loop)
      #t))
    But contradict-halts is non-sensical: if it halts, it loops infinitely; if it doesn't halt, it evaluates to true and halts. This means something in the program must not exist. I'm pretty sure true exists, and we know how to define infinite-loop, and if seems likely to exist (and its worked well for us so far). So, it must be halts? that cannot exist.

    Who was the first object-oriented programmer?

    By the word operation, we mean any process which alters the mutual relation of two or more things, be this relation of what kind it may. This is the most general definition, and would include all subjects in the universe. Again, it might act upon other things besides number, were objects found whose mutual fundamental relations could be expressed by those of the abstract science of operations, and which should be also susceptible of adaptations to the action of the operating notation and mechanism of the engine. Supposing, for instance, that the fundamental relations of pitched sounds in the science of harmony and of musical composition...
    Ada Byron, 1843

    And they showed me really three things. But I was so blinded by the first one I didn't even really see the other two. One of the things they showed me was object oriented programming they showed me that but I didn't even see that. The other one they showed me was a networked computer system...they had over a hundred Alto computers all networked using email etc., etc., I didn't even see that. I was so blinded by the first thing they showed me which was the graphical user interface. I thought it was the best thing I'd ever seen in my life. Now remember it was very flawed, what we saw was incomplete, they'd done a bunch of things wrong. But we didn't know that at the time but still though they had the germ of the idea was there and they'd done it very well and within you know ten minutes it was obvious to me that all computers would work like this some day.
    Steve Jobs (on seeing a Smalltalk demo on his 1979 visit to Xerox PARC)

    Bjarne Stroustrup. What is "Object-Oriented Programming"?. Proceedings of the First European Software Festival, 1991.
    Daniel Ingalls. Design Principles Behind Smalltalk. BYTE Magazine, August 1981.

    Who invented the Internet?

    Available within the network will be functions and services to which you subscribe on a regular basis and others that you call for when you need them. In the former group will be investment guidance, tax counseling, selective dissemination of information in your field of specialization, announcement of cultural, sport, and entertainment events that fit your interests, etc. In the latter group will be dictionaries, encyclopedias, indexes, catalogues, editing programs, teaching programs, testing programs, programming systems, data bases, and — most important — communication, display, and modeling programs. All these will be — at some late date in the history of networking - systematized and coherent; you will be able to get along in one basic language up to the point at which you choose a specialized language for its power or terseness.
    The Computer as a Communication Device, J.C.R. Licklider and Robert W. Taylor, Science and Technology, 1968.

    Gerard Holzmann and Bjorn Pehrson, The Early History of Data Networks, 1994. [Book from Amazon]

    David Evans
    University of Virginia
    Department of Computer Science
    		 evans@virginia.edu