Jonathan Magen
4y ago
Computers and Stuff
My secret shame as a computer scientist is that I can't make curly braces on a chalk/whiteboard. Also, I'm bad at proofs.
From the moment I opened my first discrete math textbook in 10th grade (a thoughtful gift from a high-school math teacher), I was confused by proofs. Logic and sets make plenty of sense, but I continued to struggle even in college. While I understood their importance and could follow the mechanics of others' proofs, I could never get my own attempts off the ground. This made me feel absolutely horrible and contributed tremendously to impostor syndrome which plagues me even today.
I wish I could tell you that sticking with it allowed me to break through the wall of understanding by sheer force of will. Nope. Instead I needed to change my approach.
There is more than one way to learn something.
If the textbook and lecture approach doesn't work for you, much like it didn't work for me, read on to see how I used some unexpected tools to help me get over the hump.
In truth I have a learning disability slash superpower where I can't understand something until I can program it. On the other hand, once I can program something I have a pretty good handle on the concept. In this case, that meant that being able to program proofs was the way for me to understand proof theory in general. But maybe not in the way you think!
Thanks to software known as proof assistants, here's how it all came together.
#1. The sequent calculus was my gateway drug.
The first proof assistant I had encountered was an interactive tutorial for the Sequent Calculus published by MIT.
Discovering (and understanding) that alternative proof systems even existed may have been enough. Then, the proof assistant itself helped me to experiment and play around whole growing my understanding of the goals. It was here that I figured out that proving a theorem is little more than showing it's a tautology!
#2. I struggled so much with Coq, but found more success with alternatives.
If you Google around for proof assistant software you'll undoubtedly make your way to Coq. Despite several attempts to wrap my head around Coq, it wasn't clicking. That's when I discovered various alternatives such as Lean, Cicada, Agda, and others.
#3. Formal methods became the light at the end of the tunnel.
After looking into proof assistants I was able to make it real in large part due to formal methods tools like Alloy and TLA+. My ability to understand and use such tools is in large part due to the work of my friend Hillel Wayne. If you don't know his stuff, check it out.