CSE 111, Fall 2004

Great Ideas in Computer Science

Course Summary

Original: 15 December 2004
Last Update: 19 September 2013

Note: NEW or UPDATED material is highlighted

NOTE: Since most of this year's freshmen were born around 1986, and this girl looks to be about 5 years old, she's approximately of your generation!

  1. Computer science is the science of computers and computing.

    (Other definitions: CS is the science of procedures;
    CS is the science of information processing, etc.)

  2. Algorithm for a problem:

  3. A problem is computable means that there is an algorithm (expressed as a computer program written in some programming language) that solves the problem.

  4. digital computer

  5. The Great Ideas of CS:

    1. Boole's & Shannon's idea:

      Only 2 nouns are needed to represent all information about any computable problem:

      • e.g., 0, 1

    2. Turing's idea:

      Only 5 verbs are needed to express the basic computable actions that can be done with those objects:

      • e.g., moveleft, moveright, print-0, print-1, erase

    3. Boehm & Jacopini's idea:

      Only 3 rules of grammar are needed to combine these nouns and verbs into descriptions of more-complex actions:

      • sequence (BEGIN S1;S2 END),
      • selection (IF <test> THEN S1 ELSE S2),
      • repetition (WHILE <test> DO S1).

      • A useful 4th rule: DEFINE-NEW-INSTRUCTION <new-instr> AS <old-instr>
      • A useful 5th rule: recursion (see below)

    4. Church-Turing Thesis:

      Nothing else is needed; more precisely:

      • A problem is computable means that there is a Turing-machine program (or a Karel program, or a Java program, or ...) that can solve it.

      • All programming languages are equally powerful.

        • But some are better than others for expressing and solving some problems, while others are better for other problems.

      • Everything that is computable can be computed by a Turing machine.

    5. Turing's Theorem:

      There is a Universal Turing Machine that can compute anything that is computable.

      • I.e., a stored-program computer; e.g., a PC, a Mac, etc.!

    6. Halting Problem:

      An example of a non-computable problem

      • There is no single computer program that can tell you whether any given computer program will halt.

  6. The first Great Idea: Binary representation:

    1. A paradox:

  7. The second Great Idea: Turing machines:

  8. The third Great Idea: Boehm & Jacopini's theorem about structured programming

  9. Artificial Intelligence: Is cognition computable?

Text copyright © 2004–2013 by William J. Rapaport (rapaport@buffalo.edu)
Cartoon links and screen-captures appear here for your enjoyment.
They are not meant to infringe on any copyrights held by the creators.
For more information on any item, click on it, or contact me.