suspension of criticisms

In grade 7, I was (re?)introduced to music. I wasn't curious enough to use Kazaa or care enough to download music on my own accords. In fact, I didn't really listen to music at all. That is, until I had a friend who started sharing Chinese music with me. We had dial-up back then, and I remember it taking forever.

Since I didn't listen to songs very often, I was easily distracted by the details. I told him why I didn't really like each particular song -- this part of the lyrics seemed so cheesy, that sound there seemed uncalled for, and that random bit of Japanese is weird... Oh, and please don't send me another English song! They're so awkward.

Did I know anything about music? Actually, not really. I didn't. All I knew was that the songs didn't sound "right", whatever that was supposed to mean. I was just like one of those arrogant literary critics who pretended to know.

Yet as I listened to more and more music, these details stopped bothering me. This seemed counter-intuitive at the time. Have I merely accustomed myself to mediocrity?

I'd like to think that at some time or another, I just got the point. There are different levels that I could focus on: there's the level of the individual sounds, and there's the level of the song as a whole. When I learn to suspend my criticisms (much like the "suspension of disbelief"), I learned to appreciate a song as a whole and became more forgiving. It was no longer about "how many things about this song I would change", but the appreciation of the message. I focused more on connecting with it, emotionally and otherwise. I could do that without the song being absolutely perfect.

"But the individual sounds are important!" Sure. I'm not saying that we should shun all criticisms. But sometimes, it is worthwhile to let the details slide for a moment, just to gauge the actual message being sent. The arguments might still hold regardless of innocent mistakes.

It's always easier to criticize than to create, but it's much more worthwhile to give someone the benefit of the doubt and to focus instead on the message they're trying to send.

End of Entry

2009 in retrospect

Writing a review blog is quite an indulgence, but this year I can actually get everything to fit in one bite-size entry. Here goes:

So the year 2009 started off terribly. Winter 09 was a disappointing term, and I quickly lost interest in everything. Luckily, life brought me to San Francisco in May-Aug 09. Working at Tagged doing programming was not something I was immediately comfortable with, but it definitely helped me grow. I finally learned that being afraid to be busy is not going to cut it, and went all out in Fall 09. I may have ridden on borrowed momentum (borrowed from... a certain person. You know who you are.), but that momentum sure helped me thoroughly enjoy this term. As for how I did in keeping my resolutions from last year, it's as you might expect. "Don't go nuts" was fine for the most part. "Don't be lazy" - not quite.

My resolution will change completely this year. In fact I have already done the switch. This new resolution is:

Focus on what's important.

It's simple, really. Focusing at the right "level" and looking at things the "right" way solves a lot problems. Not being lazy and not going nuts will be the consequences.

Actually, I need to add another resolution:

Declare major!

No comment on this one.

Let's end with notable moments in the past year, whatever I can remember: HSU Go Tournament, Waterloo Go Tournament, GEB, London Life and co-op drama, spring + winter trip to Rochester, Ghirardelli's / Pat's / Gelato / Tuk Tuk / Indian, hills across golden gate, a tuque, an epiphany that I'm supposed to have soon, the tactile dome, data center field trip, LA, pets gold/cash drama, jogging at the beach, balancing on the exercise ball, masala bay, the man that died in 95, sugar sammy, tutorial center, "Suppe mit nichts", collaborating using etherpad for cogsci exam ....

... and hopefully I'll have a tad more to add in the last 15 days of the year =)

End of Entry

Gödel's theorems -- transcending transcendence

It occurred to me that perhaps I should have preceded the previous post with this one, a discussion about the consequences of Gödel that would answer the question "so what?" So what if Principia Mathematica is never going to contain all of mathematical truth? What does that have to do with anything?

Logic is Inadequate

Gödel's Incompleteness Theorem exposes a glaring weakness in any formal system. It points at a strange disconnect between logic and truth. The beauty and austerity of formal logic become questionable -- we can't know everything there is to know about the world using formal, deductive, logical reasoning!

I guess this is old news. But personal experience suggests that it is still easy to fall for the misconception that deductive reasoning is somehow "better" than other types of reasoning. Yes, it is much cleaner, but heuristics, induction, abduction and analogical reasoning are so much more powerful, and play such an important role in intelligent behaviour.

Truth is Weird

Gödel's theorem shows that there are lots more subtleties in truth than we give it credit for. Perhaps the crux of Gödel's result come from our misunderstanding of what truth really mean in our world. I guess the other question is: what exactly do mathematical truths mean in our world? Especially strange results like the Banach-Tarski paradox, so called the paradoxical decomposition of spheres...

Argument against strong AI

J.R. Lucas argued using Gödel's Incompleteness Theorem that machines can never be as intelligent as human beings. He argued that since machines are inevitably formal systems, Gödel's Incompleteness Theorem applies. Thus, there must be some truth that machines ought not to be able to discover, but that humans can -- we can follow the construction from the last post to construct a statement that means "this theorem is not provable by the machine". While we know that this statement is true, the machine would never be able to prove or disprove it. Thus humans will always have the upper hand.

Although this is an appealing argument, consensus is that it doesn't quite work. Two of the possible arguments against Lucas are:

1. In order for Gödel's theorem to hold, we must assume that the formal system is consistent. Computers need not be to be a consistent formal system. (Humans are quite inconsistent as well.)
   
2. There are paradoxical sentences that humans cannot assign truth value to; thus perhaps we are formal systems that are more powerful, but not something that cannot be surmounted by computers.

A common theme

Themes that come up in Gödel's theorem and its proof are quite ubiquitous. The futility of the formal system in attempt to "break out" of its bound of incompleteness is like Escher's dragon, below, trying to break out of the 2-dimensionality of your screen.


There's a certain "zen"-ness to all this. Even the distinction between provability and unprovability is very much like the concept of the knowable versus the unknowable. The existence of an unprovable statement is akin to the proposition that there will always be unknowable truths. (Reminds me of this quote from Douglas Adams, the first one under "The Universe", for some strange reason)

The common theme here is, I believe, the desire to transcend, coupled with the inability to transcend. If right now, someone asked me to bet on what the meaning of life is, then I would put on my "pretend to be Zen" hat and answer: to transcend transcendence.

End of Entry

Gödel's First Incompleteness Theorem -- an intuitive sketch of the proof

In the early 20th century, Whitehead and Russell published a book called Principia Mathematica. In it the authors attempted to derive all mathematical truths from a finite set of axioms and rules of inference. The consensus amongst mathematicians at the time was that this was doable, and that it would make mathematics a lot more rigorous than it is even now.

But Gödel proved that such attempts would always end in vain. Gödel's First Incompleteness Theorem states that any consistent formal system strong enough to contain the natural numbers is incomplete. In other words, there will always be a mathematical statement whose truth value Principia Mathematica would not be able to determine.

Gödel showed this in a sneaky way, yet the logic of his proof is actually not too complicated. Essentially what Gödel did was to translate Epimenides's paradox ("this statement is false") into a formal language. I will give an intuitive and informal sketch of the proof below.

Preliminaries

A formal system consists of a formal language (a set of words/symbols, with some sort of formal grammar), and a set of rules of inferences that can be applied to an axiom or a previously derived theorem. Here, a theorem is just a statement in the formal language that is derivable from either an axiom or from a previously derived theorem. The rules of grammar and rules of inferences need to be algorithmic, meaning that one should be able to apply the rules symbolically or syntactically, without looking at the semantics.

This algorithmic aspect of grammar and rules of inference are important in determining what is expressible in the system. An English statement is expressible in our formal system if there is a statement in the formal language that have the same interpretation -- that is, we can "translate" the English sentence into a statement in our formal language.

We will assume here that our formal system is strong enough to contain the natural numbers, and that concepts such as equality, addition, existence, etc... can be expressed in it.

Expressibility of theoremhood and proofs

The most important aspect of Epimenides' paradox is self-reference. If we are to create self-reference in our formal system -- specifically self-reference about truth-hood -- we must be able to express the notion of a theorem and a proof within the formal system. Gödel showed that we can.

Statements in our formal system are nothing but a series of symbols in our formal language. But there is nothing special about the actual symbols being used. In particular, we can use natural numbers to replace those symbols. As a very arbitrary example, if we are using symbols "=", "1", and "0", we can replace every instance of "=" with 131, "1" with 101, "0" with 100 etc. Then our statement "1=1" becomes 101131101, and 101131100 can be interpreted as "1=0". Similarly, we can translate any statement in our formal system into a natural number. This natural number is commonly referred to as the Gödel numbering of a statement.

Likewise, a proof of a theorem is no more than a sequence of statements, with some special properties: that every statement in the sequence is either an axiom, or derived via a rule of inference from a previous statement in the sequence. We can represent a proof P using a natural number as well, by concatenating the Gödel numberings of each statement.

Now, note the following:

(1) Since our rules of grammar are algorithmic, it is possible to check algebraically whether a natural number S is a Gödel number of a syntactically correct statement ("=32" is not syntactically correct, whereas "1=2" is).

(2) Since our rules of inferences are algorithmic, we can translate these rules into numerical operations. We can hence check (algorithmically) whether a natural number P is a valid "proof" for a "statement" S, another natural number.

This is enough to show that the notion of proofs is expressible in our formal system -- we can make a statement called Proof(P,S) that is true if and only if P is a valid "proof" for the "statement" S (note P and S are both natural numbers). Now, the statement Provable(S) := There exists P such that Proof(P,S) would be true if and only if S is provable. We have succeeded in expressing provability inside our formal system.

The Fun Part!

A free variable is a variable that is not defined in the statement. For example, in the statement "b+b=2", b is a free variable. Let's call a statement with one free variable a class-sign. Some examples of class-signs are "a+0=1", and "there exists b such that b*b=a". Examples of non-class-signs are "1+1=2", "there exist b such that b+b=2" and "a+a=b".

We can assume that these class-signs are somehow ordered and numbered, say R_n is the nth class-sign*. We can also use R_n(k) to denote the statement one gets when replacing the free variables in R_n with a known number k. Again as an arbitrary example, if R_2 is the statement "a+0=1" then R_2(10) is the statement "10+0=1". If R_9 is the statement "there exists b such that b*b=a", then R_9(9) is the statement "there exists b such that b*b=9".

Now let's define a set K consisting of natural numbers. A natural number n is in K if and only if R_n(n) is not provable. That is, n is in K <=> ~Provable(R_n(n))

As before, R_n(n) is the statement you get when you substitute the free variable in R_n with the natural number n. In the example above, R_2(2) is an unprovable statement "2+0=1", so 2 would be in K. In contrast, R_9(9) is a provable statement "there exists b such that b*b=9", so 9 would NOT be in K. **

Note that checking provability, finding the ordering of the class-signs, and everything else we've done thus far are algorithmic operations. This is important, because it implies that the statement "n is in K" is expressible in our formal system -- that there is a statement in our formal system that corresponds to "n is in K".

But this statement "n is in K" has only one free variable, namely n, so it is a class-sign! So we can make the following modus ponens argument:

(1) "n is in K" is a class sign

(2) Class signs are enumerated by R_n

.'. (3) there must be a natural number q with R_q = "n is in K"

Now the question is, is q in the set K?

The Pitfall

If q is in the set K, then R_q(q) is not provable. But R_q(q) is the statement "q is in K", which must be true by assumption -- a contradiction. If q is not in the set K, then R_q(q) must be provable, which means q must be in the set K -- again we have a contradiction. This is Epimenides' paradox, and the statement "q is in K" is the undecidable proposition that will forever stump Principia Mathematica.

What this proof is missing

The construction I followed is from a translation of Gödel's paper, which contains the rigorous proof as well as a quick sketch. It has the advantage of providing a quick proof without complicated constructions. I tried to also take ideas from a more elegant (but time-consuming) construction in Hofstadter's book, Gödel Escher Bach. Hofstadter puts more emphasis on core concepts that are quite well hidden here, such as the concept of quining. Hofstadter also writes about the consequences of Gödel's theorem in philosophy, biology, and AI, which is nothing short of being fascinating.

End of Entry

Notes:

* We can do this, since (1) the natural numbers are countable, (2) class signs are a subset of statements in our formal system, which can be represented by natural numbers, so (3) the set of class signs have cardinality less than or equal to the natural numbers.

** Unprovability and provability of R_2(2) and R_9(9) are based on the assumption that our formal system is powerful enough to contain truths about the natural numbers. The two statements given are pretty basic truths about the natural numbers, so I would hope that they are provable/unprovable ...

More notes:

Thanks to Lilly for helping to ensure that I wrote something sane. =)

Elevator Algorithms

In Philadelphia, I spent a lot of time waiting for elevators. I inevitably paid a lot of attention to the control algorithms used by different elevators in different buildings.

All elevator algorithms solve the same type of optimization problem: given that a building has n floors and m elevators, how could we most efficiently move people up/down the floors? I'm sure you already know of the simple algorithm that every elevator implements, but one can definitely improve on this. Here's one improvement someone tried to make.

Example #1:
This building has one elevator, and 8 floors. The elevator was made to move back to floor 4 when it is idle.

This is an intuitive solution. Since there are n floors where people could call the elevator, why not minimize the wait time by making the elevator go back to floor n/2 when it is idle? The problem with this argument is that it assumes that an elevator is equally likely to be called from any of the n floors, which is not true. In most cases, people who use the elevator would use it to either go down to ground floor from the floor they're at, or up from ground floor to the floor they should be in. This means that approximately half the time, elevator request would occur at the ground floor. A better design is the following:

Example #2:
There are no more than 10 floors (I believe it was less), and about 6 elevators. When an elevator is idle, it moves to the ground floor, and opens its door.

This speeds things up a lot. Not only could you avoid waiting for the elevator to get to the ground floor, you don't even have to press the button and wait for the door to open! I thought that this was a great idea! (An acquaintance pointed out, though, that unsuspecting people might mistakenly think that the elevator is broken. Well then...)

The algorithm used in example #2 focuses a lot more on people going up as compared to people going down. I think this makes sense. Going up stairs takes a lot more effort than going down stairs, so people are more likely to use the elevator to go up. However in a building with more floors, more people would want to use the elevator to go down, so having all the elevators in ground floor is not going to help. Here's a solution that seems to work well:

Example #3:
This building has two elevators and ~12 floors. It is programmed to ensure that at least one elevator is on the ground floor at any given time. The other elevator is often seen on floor 6, but I'm not sure if there's a pattern here.

This makes a lot of sense. The first elevator takes care of the case where people want to go up from floor 1. The second elevator takes care of the case where people would want to go down, and since the elevator is at floor 6, the wait time is reduced.

For small n and m, I really can't think of a better solution than the one used in example #3. For larger n and m, though, it becomes more complicated:

Example #4:
This building has about 38 floors, and at least 12 elevators. The elevators are divided into two groups: the first group goes to floors up to 22. The second elevator skips all the floors until floor 22, so it stops at floors 22-38 (and the ground floor).

It would be quite disastrous if the elevators aren't organized this way. Imagine working on the top floor and having to wait for the elevator to stop at every floor in between! This elevator is designed to go super fast from the first to the 22nd floor, making things even more efficient.

All of these examples are real. What I don't understand is why so many buildings do not have these optimizations built into their elevators. Implementing these changes cost almost nothing, but can save a lot of peoples' time in the long run.

End of Entry