Mathematical Insights in ComputingJunction 2014

Problem-solving meets philosophy as we explore mind-blowing ideas from the theoretical study of complex systems: computers, minds, and beyond.

“Try a hard problem. You may not solve it, but you will prove something else.”

Supplementary Notes, via MIT 6.045

Week 6 – Cryptography and More

Day 23: Course Review Quiz Game

Day 22: Firestorm

Day 21: Interactive Proofs

Covered in class: Interactive proofs. Additional resources – Sipser 10.4.

Homework: Prepare to teach your Firestorm class on Wednesday! Remember, 5 minutes.

Other resources:

Day 20: Factoring and Cryptography

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.

Other resources:

Week 5 – NP-completeness... and beyond!

Day 19: Introduction to Cryptography

Covered in class: The one-time pad -- the only perfectly-secure cryptography. We also played the card game Kemps in class.

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?

Other resources:

Day 18: Prime Number Crash-Course

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.

Day 17: DNA Computing

Covered in class: DNA origami and DNA computing. The Knights’ Problem (paper and slides).

In-class problem-solving: handout. (solutions)

Reading, due Wednesday: read Computing with DNA by Leonard Adleman. Answer these questions (handout).

Other resources:

Day 16: NP-completeness

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

Other resources:

Week 4 – The P versus NP Problem

Day 15: P versus NP

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?

Other resources:

Day 14: P versus NP Continuation of Day 13

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

Reading, due Thursday Monday: The Status of the P Versus NP Problem by Lance Fortnow

Other resources:

Day 13: Exponential Growth and Asymptotic Analysis

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

Other resources:

Monday – no class – Junction puzzle hunt

Week 3 – Logic and Philosophy

Day 12: Gödel’s Incompleteness Theorems

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

Other resources:

Day 11: Artificial Intelligence

Covered in class: Searle’s “Chinese Room” argument (a.k.a. Day 10’s reading). We debated it.

Other resources:

Day 10: Logic and Paradoxes

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.

Other resources:

Day 9: Information Theory

Covered in class: Shannon entropy. Huffman encoding. Kolmogorov complexity. Additional resources: Sipser 6.4.

In-class problem-solving: The Heads and Tails of Huffman (solutions).

Homework: The Limits of Reason by Gregory Chaitin. Write: In one or two sentences, describe why Chaitin’s Ω is uncomputable.

Week 2 – Computability

Day 8: The Busy Beaver Function

Covered in class: notes. Check out a demonstration of BB(3) or BB(5) using TMSim.

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?

Other resources:

Day 7: More on the Halting Problem: Oracles and Reductions

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.

Also, finish the TMSim challenge problem! (TMSim program) (template)

Other resources:

Day 6: The Halting Problem, and Sizes of Infinity

Covered in class: Halting Problem and Sizes of Infinity..

In-class problem-solving: Sizes of infinity.

Homework: (optional) Read Sipser, chapter 4. No assignment.

Other resources:

Day 5: Turing Machines

Covered in class: notes. Additional resource: Sipser 3.

In-class problem-solving: Turing-completeness.

Homework: read Sipser, chapter 3. (No assignment.)

This week’s challenge problem: Turing Machine simulation. (TMSim program) (template)

Other resources:

Week 1 – Computing Machines

Day 4: Context-Free Grammars

Covered in class: Sipser 1.4 (the Pumping Lemma) and Sipser chapter 2 (context-free grammars and pushdown automata).

In-class problem-solving: Grammar Rules (solutions) and CFG problems (solutions).

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.

Other resources:

Day 3: Finite Automata and Regular Languages

Covered in class: sections 1.1, 1.2, and 1.3 of Sipser, chapter 1.

In-class problem-solving: aw-TOM-uh-tuh (answer key). Problems about regular operations (answer key).

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.

Day 2: Circuits

Covered in class: Boolean logic; logic gates; Boolean circuits; base 2 / binary; De Morgan’s laws; NAND and functional completeness; adder circuits; CMOS gates

In-class problem-solving: Problems and Select Answers.

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.

Other resources:

Day 1: Fractals and L-systems (half day)

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.

Other resources:

Before Junction

Refer to the Course Syllabus.


Solve these for glory and Junction Cup points.

  1. (Day 1) Prove that this L-system –
    Start - B. Rules - A goes to AB; B goes to A.
    – generates the Fibonacci sequence.
  2. (Day 2) How many possible 2-input logic gates are there?
  3. (Day 2) Problem 4 of the “Circuits” day’s problems: create the Three-inverter Logic Gate using only two NOT gates and as many AND/OR gates as you please.
  4. (Day 3) Are the regular languages closed under intersection? If not, find a counterexample that demonstrates this is not the case: two regular languages, A and B, such that A intersect B is NOT regular.
  5. (Day 7) How many points (countable or uncountable infinity) are there in a 2-dimensional square, with line segments of length 1 on each side? How many points (countable or uncountable infinity) are there in the xy-plane? Prove your answer by giving a mapping from points to some other set which you know the size of.
  6. (Day 8) Give a reduction from HALT to BLANKHALT by describing code for a Turing machine that would solve HALT using an oracle for BLANKHALT.
  7. (Day 9) How many possible Turing machines with n states are there? (State any assumptions you make about how Turing machines are specified, along with your answer.)
  8. (Day 10) Show Curry’s Paradox using set theory notation instead of implications.
  9. (Day 12) Write a quine in your favorite programming language. (Or your least favorite. Or any old programming language, really.) Remember, the English quine is:
    Say the following twice, the second time in quotes. “Say the following twice, the second time in quotes.”
  10. (Day 20) Investigate: when is g a generator mod m? When is it not? What are the rules? You need not discover the rules to receive a bonus point – just explore, and tell me about what you find.
  11. (Day 22) What sort of procedure could we use, as a class, to create a schedule that is guaranteed to be "randomized" in such a way that nobody, not any of you nor I, has control over the final schedule, and everyone is satisfied that this is the case?
  12. Implement AND, OR, and NOT using the Fredkin gate, proving that the Fredkin gate is universal.