(This post was originally posted to Metacog.)
I learned three new things today:
The first happened as I was coming out of the undergraduate office in COM1. I sat next to Yipeng, took out my laptop, and got thrust - almost immediately - into a conversation with a friend of his, Chris. Chris is a tutor for CS1231. He also happens to love mathematics.
Chris told me about this cool thing he had learnt last semester (the module he took is called Logic in Computer Science, and it's pretty darned crazy). The idea is called intuitionism. It goes something like this:
Let a and b be two irrational numbers. Is it true that ab is a rational number?
It turns out that this statement will always evaluate to true, regardless of how you look at it. A simple example of this is how √2√2 evaluates to an irrational number (and is therefore false). And yet, when you have (√2√2)√2, you get two irrational numbers that evaluate to a rational one. So this means that the statement "ab is a rational number" can both be true and false: either ab is rational, OR it is irrational, and which it is really depends on the numbers. What you have now is an OR evaluation. And we all know that a false statement OR a true statement always evaluates to true - in other words, you have a tautology.
An English example:
It is World War 2. I am enlisting to go to the frontline. I know for sure that I will or will not be killed. One of the two will certainly happen, I just can't show which. But taken as a whole, my statement "I know for sure that I will or will not be killed" is a true statement!
Well that's obvious! I said. How is this useful to computer science?
Chris grinned. "So you probably think you're smart right? That this is not beyond you? Well now try something: as a budding computer scientist, write a piece of code to prove this exact same statement."
A long silence, as Shawn and I pause to consider this puzzle. We take maybe half a minute of silence and some serious internal code-crunching before Chris cuts in: "Let me give you a hint: it is impossible to write code that evaluates that truth statement."
Wait ... what?! we said.
The reason for this, in turns out, lies in the above example of the WW2 soldier: "One of the two will certainly happen, I just can't show which." Computers can't handle things that you cannot show. And this problem - called Pv¬P, cannot be proven computationally. Chris told us that there are two kinds of logical evaluations: classical and intuitionistic logic.
Classical logic is concerned with truth. But intuitionism is concerned with justifiability. That is: if you have something like the Pv¬P problem you have something you can agree is true, but which you can't prove because you have no way to justify that conclusion. In the case of the WW2 soldier you can't prove which of the two cases it is (killed or not killed); in the case of √2√2 you have something that may or may not be irrational.
And the link to computer science - what of it? Intuitionism, Chris says, is how you know if something is computable or not.
The second lesson I learnt today is that it pays to develop focus. I spent a full afternoon programming with Yipeng and Shawn and Low Wee, but only in the last couple of hours did I get good work done. I'm not sure if this is a focus problem - I didn't really waste time the first couple of hours, having spend all that time reading and gaining my bearings in the code - but I certainly have to train my ability to focus for longer and longer periods of time. I'm currently on 15 minutes per block of work (with a 2 minute rest in between); I hope to increase this to 20 minutes soon enough.
The third lesson today is that I have learned (or relearned!) how Python is truly beautiful. I am amazed at the level of readability inherent in Yipeng's code: I glance through it now and I usually have a good idea of what's going on. In any other language this can be attributable to programming best practices; in Python certain best practices are forced upon you. Funny - to think we used Python because Yipeng wanted an excuse to pick it up!
