Thank you all for your clever questions, for your insightful problem-solving, and for your enjoyable Firestorm presentations! It was a pleasure to teach you all, and I hope you enjoy the rest of your summer.
Slides from the quiz review game
Booklet of puzzles that you all submitted
Present a 5-minute class to your peers!
Covered in class: Interactive proofs. Additional resources – Sipser 10.4.
Homework: Prepare to teach your Firestorm class on Wednesday! Remember, 5 minutes.
Covered in class: Diffie-Hellman key exchange example and the RSA cryptosystem. Additional resources – Sipser 10.6.
Reading: None today! Optionally, you can try to install PGP and get yourself your very own public/private key. I would be happy to sign your PGP key. Let me know if you encounter any issues.
Reading, due Monday: read The Limits of Quantum by Scott Aaronson. Write: If P is not equal to NP, might it still be possible that certain methods for cryptography -- which rely on factoring being hard -- might be broken?
Covered in class: All about prime numbers.
Reading, due Thursday: read Quantum-Mechanical Computers by Seth Lloyd. Write: Presumably you had some preconceived notions about quantum computing. Name one thing that you learned about quantum computing that was unexpected or that surprised you.
Covered in class: NP-completeness. Cook-Levin theorem and CircuitSAT. NP-completeness reductions: 3-coloring widgets, Super Mario widgets, and Pokemon widgets. Additional resources: Sipser 7.4, Sipser 7.5.
In-class problem-solving: 3-coloring, Super Mario, and Pokemon.
Reading, due Tuesday: read section 2 (“The Basics”) and section 3 (“Soap Bubbles et al.”) of NP-Completeness and Physical Reality by Scott Aaronson. Write: What “experiment” does Scott Aaronson perform, and how do you interpret the results?
Optional, but enjoyable, are the first two paragraphs each of section 6 (“Relativity and Analog Computing”), section 8 (“Time Travel Computing”), and/or section 9 (“‘Anthropic Computing’”).
Covered in class: P, EXP, and NP. Two definitions of NP: as "non-deterministic Turing machines' polynomial time" and as "things you can verify in polynomial time". Additional resources: Sipser 7.1, Sipser 7.2, Sipser 9.1.
In-class problem-solving: P versus NP problems.
Reading, due Monday: The Status of the P Versus NP Problem by Lance Fortnow. Write: Why would a solution to the P versus NP problem be important for mathematics?
Covered in class: Reviewed how to use big-O notation. More on asymptotic analysis and analyzing algorithms. Finished up the problems from yesterday. Introduced P and EXP (and PSPACE and EXPSPACE). Additional resources: Sipser 9.1, Sipser 9.2 (but both are highly detailed in a way that is beyond the scope of this course).
Monday: The Status of the P Versus NP Problem by Lance Fortnow Thursday
Covered in class: Big-O notation. Sorting functions by how fast they grow. Additional resources: Sipser 7.1.
Reading, due Wednesday: None today!
Challenge Problem, due Wednesday: Week 3 challenge problem – see the relevant section of these problems.
In-class problem-solving: handout
Covered in class: Gödel’s incompleteness theorems, and proof. Quines and Gödel numbering.
Reading, due Tuesday: Minds, Machines, and Gödel. Be warned: it is somewhat dense and philosophical. Don't fret over every word.
Write: “What argument does the author use that connects Gödel’s theorems with Searle’s ‘Chinese Room’ argument?”
In-class problem-solving: handout
Covered in class: Searle’s “Chinese Room” argument (a.k.a. Day 10’s reading). We debated it.
Covered in class: Valid vs. sound arguments. Consistency, completeness, and soundness of logical systems. Short history of mathematical logic.
In-class problem-solving: Puzzles from To Mock a Mockingbird (email me to ask for the handout)
Homework: Is the Brain’s Mind a Computer Program? by John Searle. Write: Two things you agree with, and two things you disagree with. Come prepared to debate your opinion on strong AI versus weak AI with your classmates tomorrow.
Covered in class: Shannon entropy. Huffman encoding. Kolmogorov complexity. Additional resources: Sipser 6.4.
Homework: The Limits of Reason by Gregory Chaitin. Write: In one or two sentences, describe why Chaitin’s Ω is uncomputable.
In-class problem-solving: Reductions and the Halting Problem..
Homework: TMSim challenge problem due Friday! For Monday, read Who can Name the Bigger Number? and answer the question below.
Question to answer:
In Who Can Name the Bigger Number, Scott Aaronson says: "Noticing this innovation, I declared the girl’s victory without bothering to count the 9’s on the cards."
When I was judging the Bigger Number Contest that we held in class, you might note that I never bothered to count just how many nines had been written, either. Yet somehow I could still declare one person to be unambiguously the victor in each round.
What would you do, if you were judging a Bigger Number Contest? What strategies would you use? When would you have to actually count the nines, and when could you safely ignore them? What are the possible strategies that people could use, and in what order would you rank them?
Covered in class: Sipser 4.2 and 5.1.
In-class problem-solving: Decidability, recognizability, and enumeration.
Homework: read or skim Sipser 4.2 and Sipser 5.1 – these comprise the material that we covered in class today and yesterday. You should read with the aim of understanding this material better. Assignment: As before, write down one thing that you learned from the textbook, either in Sipser 3 or Sipser 4.2 and 5.1 – something new that we didn't cover in class, or something that the textbook explained more clearly.
In-class problem-solving: Sizes of infinity.
Homework: (optional) Read Sipser, chapter 4. No assignment.
Covered in class: notes. Additional resource: Sipser 3.
In-class problem-solving: Turing-completeness.
Homework: read Sipser, chapter 3. (No assignment.)
Covered in class: Sipser 1.4 (the Pumping Lemma) and Sipser chapter 2 (context-free grammars and pushdown automata).
Homework: read or skim Sipser 1 and Sipser 2 – these comprise the material that we covered in class today and yesterday. You should read with the aim of understanding this material better. Assignment: Write down one thing that you learned from the textbook – something new that we didn't cover in class, or something that the textbook explained more clearly.
Additional material: Pumping Lemma examples – some examples of proofs which involve the Pumping Lemma.
Covered in class: sections 1.1, 1.2, and 1.3 of Sipser, chapter 1.
Homework: read section 1.1 through 1.3 of Sipser, chapter 1. No reading question; this reading is for you to review what was covered in class and make sure you understand the material. It also covers the concepts in more rigorous detail.
Covered in class: Boolean logic; logic gates; Boolean circuits; base 2 / binary; De Morgan’s laws; NAND and functional completeness; adder circuits; CMOS gates
Homework: read and/or skim Sipser, chapter 0, for important mathematical background and terminology. Focus on “0.2 Mathematical Notions and Terminology.”and “0.3 Definitions, Theorems, and Proofs.” Skip anything you already know. Turn in tomorrow: write down, on a piece of paper, one to three new things you learned.
Covered in class: An introduction to this class, and its themes. A lecture on L-systems and fractals: Examples of fractals. Definition of an L-system. Interactive demonstration of the dragon curve L-system, with origami example and LSysReader program.
In-class problem-solving: Fractals and L-systems handout. (I meant to have this printed out before class, but forgot!) Bonus problem: Why does the “B, A, AB, ABA, ...” L-system form the Fibonacci sequence?
Homework: Read The Origins of Computing and answer for tomorrow: Name one thing that surprised you. Name one thing that you would like to learn more about.
Refer to the Course Syllabus.