The first day at Google was busy, exhausting, but exciting. I had a lot of orientations starting at 8am, for which I had to wake up at 5:30am and take Google Shuttle. One thing I was really worried about is whether I can spot the shuttle easily or not. But I happened to meet another intern at the pick up spot, and since he knew how the shuttle looks like, we could easily spot the shuttle. Continue reading First Day at Google
Here’s a proof that any word in a language cannot be describd within the same language.
Proof (by induction):
Assume that each word takes at least one other word to define. Also assume that circular definition is not allowed. And finally, assume that a language can be constructed by adding word one by one.
Basis: Suppose a language consists of one word. Then trivially, this word cannot be described in terms of other words in the langauge. In particular, the word cannot be described.
Inductive step: Now suppose the statement is true for k >= 1. Then add one more word T to this langauge, constructing a language with k+1 words. Now suppose the statement is false; i.e. suppose that T can be described in terms of other words. But then T must be described in terms of at least one word in the original k words. Let us call such a word S. But S must be described in order to define T. However, by our inductive hypothesis, S cannot be described. Then T that cannot be described. A contradiction. Thus any word in a langauge consisting of k+1 words cannot be described.
Hence basis and inductive steps have been proven. By mathematical induction, the statement is true. Q.E.D.
