Godel’s Incompleteness Theorem and other CS concepts

This is where I see most of my Computer Science juice sprouts out of me – the nonsense based on CS. Here’s a few gems I recalled recently:

jiinjoo says:
it’s raining
jiinjoo says:
i want to go orchard shopping
Zoidberg says:
orchard is for faggots. Why not go pulau ubin to shop instead!?
jiinjoo says:
coz, someone gave me $100 tangs vouchers
Zoidberg says:
oh, let’s share it
jiinjoo says:
are you a faggot?
jiinjoo says:
lol – this is as good as the godel’s sentence: “This Sentence Is False”

CS concept: Godel’s Incompleteness Theorem (Explained in full)

We always use this simple example to explain it:

Read the following sentence and answer whether it is true or false:
This Sentence Is False

It’s not a trick question. If you say the sentence is true, then the sentence is false because it says so. If you say the sentence is false, then the sentence is in fact true coz it says the sentence is false. If you’re not following me at all you can skip to the next blog post and see other brain dead youtube videos now.

So similarly in this conversation, Zoidberg wants to split the 100 voucher and he doesn’t want to be a faggot (from the tone of the conversation). You can see that if Zoidberg says yes (i am a faggot), then he gets to split the tangs voucher, but he’ll be a faggot. If Zoidber says no (i am not a faggot) then he gets to not be a faggot, but he’ll not be able to split the voucher. Godel basically says (in extremely loose laymen terms) that given any consistent system where you can spell out its assumptions (like this simplistic Zoidberg is not a faggot, Zoidberg wants to split tangs voucher), the consistency of the system cannot be proved in the system (i.e. we don’t know if Zoidberg is a faggot, unless we’re outside the system, e.g. you actually know who Zoidberg is and see that he is / isn’t a faggot). Phew.

Or consider the other commonly quoted parellels: “God doesn’t exist since an ultimate ruler must be responsible for all things but a perfectly just being wouldn’t be responsible for evil acts.” or “God can’t be omnipotent because He cannot create a stone which he cannot lift.” (If He can create, then He cannot lift the stone, so not omnipotent also)

Banquet Seating

In another recent thread (as a lot of my friends are getting married), there were discussions on how to arrange the guests so that the maximum number of constraints can be satisfied. The typical problem is this:

You have many guest for your wedding, say 100 of them, to be placed to 10 tables, 10 each table, as any typical hotel banquet seating. But every guest that you invite gave you specific instructions on who he would like to sit with. Here are a few examples:
Couples (and Spouses) want to sit together
Some will not sit with ex-bf, ex-gf
Naturally try to minimize strangers per table (e.g. colleagues together)
But colleagues don’t want to sit with the big boss (feels odd) etc.

CS concept: NP-Complete problems (Explained in full)

In essence, there’s no way to figure out quickly how to arrange the guest except to trial-and-error. Technically speaking, if you have no useful heuristic, you will need to brute force the problem, which is at best a O(n^2) problem, but if given a solution, you can verify it in polynomial time O(n). So, in laymen terms, if I give you a solution, you can then take my set of constraints and tick them off one by one to see this is a “valid” seating arrangement.

There are many problems like that, and it is possible to translate them from one to another. Here are some keywords to start you googling: Knapsack problem (what to carry every round within physical limits), Travelling Salesman problem (how to minimize cab fare), Trunk packing problem (remember going out as a family to a picnic?), Graph Coloring (flip open your coloring book and see if you can color shapes such that no borders border the same color, and so on, and so forth.

In the end, the wedding seating was bruted forced 🙂 But the heuristics was decent. Otherwise, you can pay to solve your problem.

Wanted to write one more on Zero Knowledge Proof and its relation with your daily password management, but looks like I ran out of time (need to go Christmas shopping!!) Hope this gives a good start for those who are always eager to know what they actually learn in a theoretical CS course and their applications 😉