This class will feel like solving a sequence of open-ended puzzles. You'll work with other students to solve these puzzles, and sometimes give mathematical arguments as to why they can't be solved. Imagine you're in a maze, but tunnels open and close based on your movement. For example, maybe there are two tunnels which can only be passed in one direction, and when you go across either one they both flip direction (we call this a "2-toggle"). Or maybe every time you go across a certain tunnel in either direction, another tunnel switches between open and closed (we call this "tripwire lock"). It's possible to put together several 2-toggles to construct something which behaves like a tripwire lock. It's also possible to use several tripwire locks to build a 2-toggle. In this class, we'll investigate which "gadgets" can simulate other gadgets. We'll play with lots of gadgets, including the 2-toggle and tripwire lock, and see what they can build. In some cases, we'll prove that certain gadgets can't simulate certain other gadgets. We might even find general-purpose simulations, showing that a particular gadget can simulate every possible gadget (or every gadget with some property). This will be a hands-on class, mostly focusing on you finding simulations for yourselves.

This class will feel like solving a sequence of open-ended puzzles. You'll work with other students to solve these puzzles, and sometimes give mathematical arguments as to why they can't be solved. Imagine you're in a maze, but tunnels open and close based on your movement. For example, maybe there are two tunnels which can only be passed in one direction, and when you go across either one they both flip direction (we call this a "2-toggle"). Or maybe every time you go across a certain tunnel in either direction, another tunnel switches between open and closed (we call this "tripwire lock"). It's possible to put together several 2-toggles to construct something which behaves like a tripwire lock. It's also possible to use several tripwire locks to build a 2-toggle. In this class, we'll investigate which "gadgets" can simulate other gadgets. We'll play with lots of gadgets, including the 2-toggle and tripwire lock, and see what they can build. In some cases, we'll prove that certain gadgets can't simulate certain other gadgets. We might even find general-purpose simulations, showing that a particular gadget can simulate every possible gadget (or every gadget with some property). This will be a hands-on class, mostly focusing on you finding simulations for yourselves.

Want to know why puzzles and videogames have no easy way to solve them? We'll look at their basic components (gadgets) and make a maze of tunnels to show how hard they can get. There will be physical models of those gadgets. We'll start by introducing some canonical hard problems, then we'll show that mazes made of certain gadgets are hard to solve, and finally, we'll prove some games hard.