Great Ideas in Computer Science

Course Summary

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.)

   • CS studies what information-processing tasks can/cannot be automated
   • how this can be done;
   • and how this can be done efficiently.
   Our focus: algorithmic problem solving

2. Algorithm for a problem:
   • a procedure for solving the problem that is:
     • unambiguous (all steps clear & well-defined for whoever/whatever executes the procedure)
     • effective
       • finite # of steps; eventually halts
       • correct solution to the 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
   • general-purpose information-processing machine
   • stores information representing real-world objects
   • modifies that information (i.e., computes with that information)

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:
   • letters, numerals, etc., can all be represented in binary notation (0/1, up/down, on/off, high/low voltage, etc.)

   • algorithms for converting between decimal and binary numerals

   • can represent negative numbers, rational numbers, and can approximate real numbers

   • can represent b&w/color images/pictures using binary bitmaps

   • can represent sound via binary sampling of continuous waves

   • program tells computer how to interpret the binary information in a storage location

   • truth values (Boolean logic) can be represented by binary values (true/false)
     • truth tables for: not, or, and, if-then, xor, nand, nor, etc.
   1. A paradox:
      • If each character (letter, numeral, symbol) is represented as a string of (let's say) 8 bits, then each 10-letter word is represented by 80 bits.

      • So, each single thing to be represented needs at least 8 times as many bits to represent it.

      • That's an 8x "magnification", so to speak.

      • Yet think how much is represented inside your own PC or Mac: LOTS of stuff, all squished into (i.e., represented as complex structures of) bits!

      • That's the paradox: Objects seem to be expanded 8 times, yet they become smaller

      • So, bits must be very small!

      • For a related topic, see:
        Lesk, Michael (1997), "How Much Information Is There in the World?"

7. The second Great Idea: Turing machines:
   • Every algorithm can be expressed in a programming language for a computer consisting of:
     • an infinite tape divided into squares, each containing "0" or "1",
     • a read/write head that can scan a square, move to the left or right, and print or erase a symbol on the square.
     • internal states that keep track of what the computer is supposed to do.

   • Turing's analysis based on how human "computers" behaved.

   • Looked at TM programs for computing truth-values, identifying palindromes.
     • Used flowcharts, "structured" notation

8. The third Great Idea: Boehm & Jacopini's theorem about structured programming
   • Karel the Robot as an example of how to do structured programming and algorithmic problem solving.

   • Karel can implement a Turing machine.
     • Therefore, can do anything a TM can.
     • Therefore, can do anything that's computable.

   • Karel's programming language: See summary.

   • recursion: defining a new instruction in terms of a simpler version of itself (requires a "base case" that is not defined in terms of itself).
     • E.g., the definition of a Karel <instruction>
     • E.g., problem solving by stepwise refinement!
     • Another version of the Church-Turing Thesis says that computable problems are those that are solvable by recursive procedures.

   • Algorithmic problem solving by top-down design & stepwise refinement:
     • An algorithmically-solvable (i.e., computable) problem P consists of "simpler" problems P1...Pn, each of which is also algorithmically solvable.

     • A solution for P consists of the solutions for P1...Pn combined via sequence, selection, and repetition (with occasional help from "define-new-instructions" and recursion)

     • Each Pi and its solution can be understood by itself (its name should be self-explanatory), and ideally should be re-usable to solve other problems.

     • The overall structure of P's solution should be understandable at each "level".

     • The simplest problems are the ones that "solve themselves"; i.e., they are ones that you already know how to solve. E.g., TM's 5 basic verbs; Karel's 5 basic instructions.

     • Can test each solution to Pi independently, and can use the structure of P's solution to debug it or to modify it.

9. Artificial Intelligence: Is cognition computable?
   • The Turing Test: If a human interrogator decides that she or he is communicating with a cognitive agent, then whoever or whatever s/he is communicating with has cognitive abilities.
     • I.e., if it is a computer, then computers can think!

   • Searle's Chinese-Room Argument: It is possible for a computer to behave in such a way that the human interrogator in a Turing Test decides that s/he is communicating with a cognitive agent, yet the computer does not have any cognitive abilities.