(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!
6 comments:
The tautology thing. I'm reminded of this think tank i came across. not sure if its a tautology BUT here it is:
BRAIN TEASER: Kingsley and Dumbledore Kick It Old School Style
You've undoubtedly often wondered to yourself what exactly the two coolest wizards ever to rock purple robes do in their spare time, and after risking our lives and carefully stalking them every day for 3 years (read: sending them a politely-worded letter and a muffin basket), we've found the answer: they play a hell of a lot of badminton. Yes, it's true: the two baddest men you can imagine get together every afternoon (as long as there are no dementor attacks or avian flu outbreaks to deal with) and hit a tiny, plastic birdy back and forth over a net for hours at a time, only stopping to cast a few sporting insults in each other's direction or chug some electrolyte-spiked butterbeer. There's nothing that Kingsley Shacklebolt and Albus Dumbledore enjoy more than a good game of badminton (other than a pepperoni pizza party in Dan Bergstein's basement), so you can imagine their great disappointment when one day, they met at the WMCA (like the YMCA, but for wizards) and found the entryway to the badminton courts completely sealed over. In its place were two new doors, each guarded by a sphinx. As Albus and Kingsley's mommas didn't raise no fools, the two men immediately deduced that they would have to answer a riddle in order to partake in their usual afternoon of lighthearted competition. Here is the riddle:
One of the doors leads to the badminton court, but the other door leads to a conference on the hazards of inadequate cauldron-bottom thickness, which is sure to be so insufferably boring that Kingsley and Dumbledore drop dead from the dullness of it. Our heroes may ask each sphinx one "yes" or "no" question before deciding which door to take, but one of the sphinxes will always lie, and one will always tell the truth. There is no way of telling which sphinx is which, and they cannot ask 2 different questions. SO: what question should Albus and Kingsley ask one or both the sphinxes to ensure that they spend their day putting Wimbledon winners to shame, and not suffering untellable pain at the hands of yet another one of Percy Weasley's PowerPoint presentations?
AND
Brain Teaser: "Everyone Hates You, Ludo Bagman"
Allow us to set the scene: You and Cedric Diggory are on an unimaginably spectacular, all-expenses-paid vacation in paradise, where chocolate milkshakes abound and the scent of bacon wafts, like a dream, through the air. You are having, quite simply, the time of your life: when you're not playing heated games of Water Quidditch, you're relaxing in hammocks, sipping on non-alcoholic strawberry daiquiris, and discussing ways to spend the 700 million Galleons that you recently found buried in the sand. You have never been happier, and you're 89% sure that Cedric is the one who has been placing the adorably misspelled love (or "platonic friend") notes under your pillow every night (if it's not him, it MUST be Joseph Gordon). But one day, while the two of you are soaking up some non-toxic rays and tucking into the most gorgeous BLTs you've ever laid eyes on, disaster strikes: 10 fearsome, furious goblins Apparate out of thin air and hold 10 shiny, newly-sharpened swords to your beautifully bronzed throats.
As you soon find out, the gang of goblins has been dangerously misinformed: someone told them that you were Ludo Bagman, and Ludo Bagman happens to owe them a gabillion, bajillion Galleons. As neither of you have your wands on hand (they’re buried in the sand 100 yards away), you are at the mercy of the goblin horde, who cannot be convinced that you aren’t Ludo (he skipped out of the country after losing a bet to them 5 months ago). What’s more, the goblins are so angry that they refuse to accept apologies or payment: they only want BLOOD. They offer you the chance to solve a riddle. If you get it right, you're off the hook, but if you get it wrong, you’re dead. After you and Cedric concernedly look around for the cabana boy and thoughtfully dunk a few French fries into your cookie dough Blizzard, you decide to attempt the riddle—after all, you really have no other option.
The goblins state that you will have a choice in your manner of death, and you are asked to make a single statement. If that statement is true, you will be crushed into a pulp and given to Dudley as a protein shake. If that statement is false, you will be chopped into a million pieces and sold on eBay. So: What single statement can you make in order to avoid being executed altogether?
Hint: The statement must predict HOW YOU WILL DIE as if your death is a certain occurence. It should either say "I will/won't be chopped into a million pieces" OR "I will/won't be crushed into a pulp." The trick is to figure out which of these statements (were their death sentences carried out) could be neither true NOR false. The statement "I will be crushed into a pulp" is always true, which means you'll die if you say it. But what about "I won't be crushed into a pulp" or "I will be chopped into a million pieces"? Apply "true" and "false" to all four possible statements, and you'll figure out which makes your death impossible!
First of all, I must say that I absolutely adore the writing in the two examples! =P So hilarious!
Both are logic examples, that's for sure. And the second one is certainly a Pv¬P puzzle.
My answers to the two (hehehe): 1) Which is the right path?
2) I will or will not be chopped into a million pieces and sold on eBay (alternatively: I will or will not be crushed into a pulp and given to Dudley as a protein shake).
Did I get it right did I did I?
Ooh, would it be cheating if you wrote a program to symbolically simplify logic statements? That way, if you fed the program "Pv¬P" it would simplify to "1". XD
Wait, I just did some extra reading on intuitionistic logic and found out that "Pv¬P = true" is NOT an axiom of the system. Back to the drawing board.
the answers are onnnnn http://www.sparknotes.com/testprep/2010/07/28/the-think-tank-give-me-diggory-or-give-me-death
:D really cool website. they write the funniest stuff ever. and answers are not really on that page i think, have to go to newer post to see the answers. quite cool :)
Post a Comment