CSE 111, Fall 2004
Great Ideas in Computer Science
Original: 15 December 2004
Last Update: 19 September 2013
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
- Computer science is the science of computers and
(Other definitions: CS is the science of procedures;
CS is the science of information processing, etc.)
- CS studies what information-processing tasks can/cannot
- how this can be done;
- and how this can be done efficiently.
Our focus: algorithmic problem solving
- Algorithm for a problem:
- a procedure for solving the problem that is:
- unambiguous (all steps clear & well-defined
for whoever/whatever executes the procedure)
- finite # of steps; eventually halts
- correct solution to the problem
- A problem is computable means that there is an algorithm
(expressed as a computer program written in some programming
language) that solves the problem.
- digital computer
- general-purpose information-processing machine
- stores information representing real-world objects
- modifies that information (i.e., computes with that information)
- The Great Ideas of CS:
- Boole's & Shannon's idea:
Only 2 nouns are needed to represent all information
about any computable problem:
- 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
- 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)
- Church-Turing Thesis:
Nothing else is needed; more precisely:
- A problem is computable means that there is a Turing-machine
(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.
- 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.!
- 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
- 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
- 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,
- 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),
Information Is There in the World?"
For another related topic, see:
physical space does the internet take up?"
And for yet another, see:
"When—if ever—will the bandwidth of the
Internet surpass that of FedEx?"
"Google's Datacenters on Punch Cards",
What If #63.
- 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"
- Looked at TM programs for computing truth-values,
- Used flowcharts, "structured" notation
- 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
- 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.
- 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.
Text copyright © 2004–2013 by William J. Rapaport
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.