Splash Biography

For Mary Queen of Scots, a broken cipher meant her execution. For the Allies during WWII, a broken Enigma code meant lives saved and war significantly shorter. When you can read your enemies' private communication, you know what they're thinking and what they're planning--and such information is never a bad thing. Come learn how to send messages that your friends won't be able to read--and even better, how to break the secret messages that other people have sent! We'll cover a few different kinds of ciphers, including Caesar shifts, substitution ciphers, and the Vignere cipher. Most of this will take the form of you all working in groups trying to break code; there will be hints if you need them.

Computers are powerful, sure. But can they compute anything you want them to? Is there anything computers absolutely can’t figure out, no matter what? The answer here is yes—computers are not omnipotent. In this class, we’ll prove mathematically that despite whatever clever algorithms people can come up with, there will always be problems that are impossible for a computer to solve. We’ll look at few examples, including the Halting Problem. Along the way, we’ll encounter and investigate a variety of theoretical constructs which compute: deterministic finite automata (DFA’s), pushdown automata, context free grammars, and Turing Machines. We'll also explore what kinds of problems these can solve--and prove which ones are more powerful.