CSE 111, Fall 2004

Course Summary

 Original: 15 December 2004 Last Update: 19 September 2013 Note: or 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.)

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

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.