Last year my friend from another UK university has told me his algorithms exam question which went along the lines of this:
Your friend from Cambridge has implemented a binary search tree. Unfortunately, due to lack of practical skills, he has made some mistakes. Help him fix it.
I found it hilarious solely because there’s a grain of truth in every joke – Computer Science degree in Cambridge is indeed pretty theoretical, with courses like Logic and Proof, Computation Theory, Complexity Theory, Semantics widespread. At some point in your degree you feel like yelling into the abyss about why are you suffering through all this stuff.
That’s where Sid comes in with his talk this week. Breaking the holy tradition of speaking about his Part II project, he spoke about the mathematical history of the foundations of Computer Science instead to convince us all that these theoretical courses are all in fact integrated in the core foundation of CS.
It all began with Russell’s Paradox of a set of all sets that don’t contain themselves. This resulted in Russell’s and Whitehead’s conclusion that the Maths is broken. To be fair, they didn’t simply break Maths and ran away giggling, but instead tried to fix it in a book called Principia Mathematica by introducing some really simple axioms and some rules which we apply to prove things. And all was good with the world until Gödel broke it again.
Sid’s translation of Gödel’s theorems to English
That made David Hilbert come up with Entscheidungsproblem (judging from the name, I guess he was angry at the time) – given a logical statement with a bunch of axioms deciding whether it’s valid. Then Alan Turing came along and thought that we can find if something is valid with what we currently think of as an algorithm. He then built an imaginary machine, Turing machine, that solved this problem and discovered that a general solution to this problem is impossible. In the meantime, Alonso Church approached this problem with lambda calculus and came to the same conclusion.
They later collaborated and came up with Church-Turing Thesis, stating that a function on the natural numbers is computable if and only if it is computable by a Turing machine, where computable means that one can compute it in his head. Furthermore, everything that can be computed mathematically can be computed by lambda calculus, while everything that can be computed by lambda calculus can be computed by a Turing machine. Great! Now we have defined our goal to make a system be able to compute computable things – we want a system to be Turing complete.
But what do we actually need to create a Turing complete system? Sid then shows that 6 things: constant function, successor, projection, function composition, primitive recursion and minimization are enough. Not satisfied, he then shows that actually 3 things are enough with SKI combinators. Not satisfied, he then shows that actually 2 things are enough since we can express one combinator through other two. Still not satisfied, he then shows that actually 1 thing is enough and introduces us to iota combinator. Since no one in the audience would’ve believed that 0 things are enough, Sid finally gets satisfied and stops.
But all of this history comes with some powerful takeaways. Computer Science essentially came about from a bunch of people thinking very hard about what it was possible for the brain, Maths or a machine to do. So in essence, Computer Science is not about programming. It’s about proving theorems, which programming is basically like. Sure, one can abstract himself from such an analogy and never go below the code level, but being exposed to theoretical foundations of CS can be proven valuable to understand the nature of this subject and as such Sid’s closing message was for everyone to try and take the most out of these courses now that they are aware of why Cambridge is teaching them.
In my opinion, it was a great talk and I really enjoyed this packed history lesson. But the most memorable part of the evening was Sid’s delivery packed with jokes at every corner including bashing PHP, using a grumpy cat, legitimately proving that P = NP, showing an XKCD comic on fetishes, deriving Andy’s banterousness, asking the audience a question where all answers were wrong, repeatedly breaking Maths, referencing popular songs by Hozier, Daft Punk and Mark Ronson, using the word “bae” and pretending that people won’t ask him questions if he asks for it.
Disclaimer: the author of this post does not claim knowledge of the post’s topic. All contents are interpreted from Sid’s talk. If something in this post is wrong, blame Sid.