Mathematical Insights in Computing

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

Teacher: Chelsea Voss

(Course Website)

Description

The existence of logical paradoxes, the mathematics of infinity, the possibility of DNA computing: We will tackle these and many other curiosities as we delve into fascinating results from theoretical computer science, the mathematical exploration of what computers can and cannot do.

Come learn how you can use prime factorization to encrypt your secrets, why there are some problems that no computer can ever solve, and what makes "This sentence is false" the surprising centerpiece of an intriguing theorem. We will explore programs that can output their own source code, debate philosophical questions in artificial intelligence, and learn about the legendary unsolved problems that have left modern theoretical computer scientists still puzzling.

Expect an exciting mixture of mathematics, philosophy, and theoretical computer science, with a focus on solving and understanding problems.

Please note that we will only study theoretical computers. Although this class will cover information that is essential for a future computer scientist to know, it will not teach programming. On the flip side, programming experience is not required.

Tentative list of topics covered

• Computability: Sizes of infinity; finite automata and regular languages; Turing machines; the Halting Problem; Busy Beaver numbers; Kolmogorov complexity.
• Mathematical Logic and Philosophy: Logic puzzles; logic paradoxes; Gödel’s incompleteness theorems; the Turing test.
• Complexity: Efficient algorithms; the P vs NP problem; the Cook-Levin theorem; NP-complete problems; DNA computing.
• Cryptography: Modular arithmetic; historical cryptography; Diffie-Hellman; public-key cryptography; RSA; zero-knowledge proofs.

For the application...

Prerequisites

Two years of high school algebra and precalculus, or equivalent knowledge.

Relevant experience

Please list the most advanced mathematics classes that you have taken, indicate your grades, and indicate whether they were honors, AP, IB, or equivalent.

Please also indicate any experiences that you have related to computer programming, mathematics, or problem-solving. School activities, books you’ve read, classes you’ve taken, hobbies and projects that you’ve done – anything you think is relevant.

Core-specific application question

The application question for this class consists of multiple parts. You should provide responses to all parts. These are designed to require some thought, so don’t be discouraged if it takes you a while to come up with good answers. You can do it!

Part 1. You Give Me a Puzzle

Tell me a good math problem or logic puzzle that you have come across, one that you that really got you thinking, wondering, and exploring. Write as if you were describing the problem to a fellow student and include enough detail for someone else to understand and try to solve your problem.

Part 2. I Give You a Puzzle

You have a simple scale—it has two sides, into which you can place rocks to weigh them. The scale tells you whether the two sides are equal, or, if they aren’t equal, which side is heavier.

There is also a store that sells Standard Rocks of known weight; there are rocks of weight 1 ounce, 2 ounces, and so on, all the way up to 40 ounces (and they have many rocks of each weight). Regardless of weight, each Standard Rock costs $10.

I give you a Mystery Rock of unknown weight; all you know is that it weighs an integer number of ounces between 1 and 40, inclusive. Your goal is to purchase as cheap a set of Standard Rocks from the store as possible, and use that set of rocks and your scale to find the weight of the Mystery Rock precisely, down to the last ounce.

You can only visit the store once, and must buy only one set of rocks that works for any Mystery Rock I give you to weigh. However, you can use your scale as much as you like.

As your answer, tell me which Standard Rocks you would buy, describe what procedure you would use to identify the weight of the Mystery Rock, and explain your reasoning. Try to spend as little money as you can: $60 or $50 are reasonable solutions. For a challenge, try for $40.

Don’t be alarmed if this problem takes you a while to solve; you can do it!