|
LSP 354: Honors Seminar in Mathematical Reasoning: Unifying Ideas in Computer Science
Lehman College, CUNY
Prof. Johnson
Spring 2015
W 1pm-4pm
Library Room 315
Without mathematics we cannot penetrate deeply into philosophy.
Without philosophy we cannot penetrate deeply into mathematics.
Without both we cannot penetrate deeply into anything.
— attributed to Leibniz (possibly apocryphal)
LSP 354: Honors Seminar in Mathematical Reasoning: Unifying Ideas in Computer Science.
We will discuss some of the fundamental ideas and discoveries of computer science, many of
which have a unifying, universalist quality, either in the sense of unifying many different
problems, methods, or models, or in the sense of (arguably) speaking to questions studied
by other disciplines.
The overall feel of the course will be something like (math + philosophy) / 2, except that
this is math and philosophy emerging from, or informed by, computer science. Much of the
discussion will be mathematically informal yet rigorous, centered on arguments, either
with or without mathematical notation. For many topics and results the goal will not be to
give a full treatment, going mathematically all the way down, but instead to see the
intuitions behind the results and their relevance to other topics. When practical, though,
we will study actual formal proofs, especially when they are simple and beautiful.
Prerequisites.
Interest in philosophical questions, aptitude for mathematical reasoning, and basic
familiarity with computers and programming. No formal course preqreqs (nothing will involve
calculus, e.g.), but logical/mathematical reasoning is important: the ability to make clear,
rigorous arguments and to find holes in bad ones.
Topics:
- Computability theory:
Turing machines and other (equivalent) models of computation (assembly, circuits,
cellular automata, quantum computers, etc.)
-- the halting problem (which proved there are problems you can't solve),
Godel's theorem (which proved there are mathematical facts that you (provably!)
can't prove), and other (near-equivalent) diagonalization-based impossibility results
(Cantor's theorem, Tarski's theorem, Russell's paradox, Groucho Marx, ...)
- Algorithms and complexity theory:
NP-Completeness (which unifies an enormous range of superficially unrelated problems and pursuits)
-- P vs. NP (is it easier to read a book than it is to write one?)
-- duality and minimax (LP, max-flow/min-cut, Nash's theorem, Brouwer's theorem, etc.)
- Inference and adaptation:
machine learning and the problem of induction (Hume, Goodman's grue,
Wittgenstein's private language argument)
-- Bayes learning and Occam's razor
-- genetic algorithms, PAC learning, and biological evolution
-- AI and (computational) philosophy of mind (Searle's Chinese room, Block's Chinese
brain, swampmen, zombies, etc.)
For most classes there will probably be preparatory reading, i.e., reading to do in advance.
Much of this reading will be hard. Really hard. (That's why we're paid the big bucks.)
Rule of thumb: If the reading seems easy, you're probably
not really getting it. In general, you should read assigned readings at least twice
prior to the class they are preparatory for. Relatedly: In general, in this or any serious
class, you should expect to spend 2-3 hours studying/working for every hour spent in class.
Some of the reading will be technical or semi-technical, e.g. including formal examples.
Read actively. This means verifying the constructions' details as they're given
("recompiling them in your head") and trying as much as possible to work them out yourself
before the "answer" is given.
We won't be following a textbook as such, but rather will read and discuss a number of several texts,
probably all of which are available free online. There will likely be several assignments
from the following, in addition to individual (online) handouts. (NB: You're not required to buy all these,
or any of them for that matter;
ask me if you need help finding something without paying for it.)
The texts below are referred to by abbreviation in the schedule. "Sect. i.0" refers to
the unnumbered text before subsection i.1 in a text.
- 1/3 - problem sets (~3)
- 1/3 - short papers (~3)
- 1/3 - participation, in several forms:
- active in-class discussion: There should never be a class where no words come out of your mouth.
- reading responses: You will submit brief responses (1-2 paragraphs, 4-6 sentences),
critically responding to one of the assigned readings, the night before every
class. Don't summarize the reading, criticize it in some way, make some point about it,
say something that struck you about it, etc.
(One possible schema: She argues that x because of y, but she ignores the effect z, which means...)
Your email must contain LSP in the subject line.
- leading individual class discussions
- possible pop quizzes
Consistant attendance and participation is mandatory and essential.
If for some reason (like, sickness unto death) you expect to or have
missed a class, please email me to let me know your reason for missing it and
borrow a classmate's notes on the class.
Don't cheat. Generally speaking, never submit any work where you're hoping I don't
discover something you know about how you produced it. (You know about the Internet, and
so do I.) In essence: don't try to mislead. Please don't do this, because it would
make me very sad. That is,
I will strike
down upon thee with great vengeance and furious anger those who attempt to poison and destroy
the compact in this way.
Instructor:
Prof. Matthew P. Johnson
email: mpjohnson@gmail.com (please include LSP in the subject line)
Office hours: Wednesdays, 1pm-2pm and 4pm-5pm. Office: Gillet 200B.
When you need help or want to talk, please come to office hours. Seriously. It's
not bad students who come to office hours; good students to office hours.
When you're going to come in, though, if possible please email me earlier in the day telling me to expect you.
I want the course to run smoothly, enjoyably and profitably. Feel free to let me know
what you find good, interesting and fun about the course. Let me know sooner about the opposite.
- PS 1
- PS 2
- PS 3
- PS 4
(Tentative) Schedule (likely to change, depending on pace and student interest)
- (1/28) intro: unifications, equivalences, dualities; philosophy -> CS; Turing machines
- (2/4) von Neumann architecture, TMs, etc.
reading: the sections above on the texts and grading; IPaOTfT, ch. 24 (assembly); WPSCACC, sect. 1.0-1.1; QCsD, ch. 2
- (2/11) UTMs, simulation, and VMs
reading: QCsD, ch. 2,3; IPaOTfT, ch. 25 (VMs, UTMs)
(2/18) no class: Monday schedule
- (2/25) the halting problem, Chaitin's Omega, reductions
reading: QCsD, ch. 3
- (3/4) Godel's theorem, and other (near-equivalent) diagonalization-based impossibility results
reading: QCsD, ch. 3; blogpost on Colbert and Godel
- (3/11) computational complexity; NP, NP-Completeness; P vs. NP
reading: WPSCACC, sect. 3.0-3.1; WCNtBN?;
QCsD, ch. 5,6; TGT, ch. 3,4
- (3/18) continue Godel, etc.
reading: same
- (3/25) finish Godel, reductions, NP-Completeness
reading: same
- (4/1) NP-Completeness, cont.; PCPs [Widgerson talk 1 and talk 2]
reading: same
(4/8) no class: spring break
- (4/15) linear programming and integer programming
reading: QCsD, p. 193-195 (PCP subsect.); QCsD, p. 180-181; WPSCACC, sect. 7.2
- (4/22) no class: tragic illness
- (4/29) induction, Occam's razor, Bayes, PAC learning
reading: WPSCACC, sect. 7.0-7.2; QCSD, ch. 16; "A Plan for Spam" and "Bayes' Theorem For Dummies"; PAC, ch. 5
- (5/6) genetic algorithms, biological evolution [GA example; Papadimitriou talk]
reading: WPSCACC, sect. 3.2; PAC, ch. 6; watch Papadimitriou lecture (in class)
- (5/13) AI and (computational) philosophy of mind [Eliza]
reading: WPSCACC, sect. 4.0-4.2, 4.3-4.4; QCsD, ch. 4 (C-T, TT, Chinese room); QCsD, ch. 11 (Godel-Penrose)
mpjohnson@gmail.com
|