Monday, November 14, 2005

Godel

Godel's theorem as it appeared in Proposition VI of his 1931 paper "On Formally Undecidable Propositions in Principia Mathematica and Related Systems I.":

To every w-consistent recursive class k of formulae there correspond recursive class-sings r, such that neither v Gen r nor Neg (v Gen r) belongs to Flg(k) (where v is the free variable of r).

which translates to

All consistent axiomatic formulations of number theory include undecidable propositions.
...
Godel showed that provability is a weaker notion than truth, no matter what axiomatic system is involved.
...

Escher

Escher takes you down Strange loop (or is he taking you up)

Two-step Strange Loop

Self-reference

Perpetual motion

Metamorphosis

More Escher pictures

Implicit in the concept of Strange loops is the concept of infinity, since what else is a loop but a way of representing an endless process in a finite way? And infinity plays a large role in many of Escher's drawings.
....
In some of his drawings, one single theme can appear on different levels of reality. For instance, one level in a drawing might clearly be recognizable as representing fantasy or imagination; another level would be recognizable as reality. These two levels might be the only explicitly portrayed levels. But the mere presence of these two levels invites the viewer to look upon himself as part of another level; the viewer cannot help but getting caught up in Escher's implied chain of levels, in which, for any one level, there is always another level aboe it of greater "reality", and likewise, there is always another level, "more imaginary" than it is.

Friday, November 11, 2005

Graduating from B.E. to B.Tech

It was August 1994. Ragging was still not banned in Andhra University. As a junior here, everyday before and after each class, whenever there was free time we were subject to bantering from our seniors. This was supposed to be an informal way of knowing your seniors :-). These seniors were from all departments of engineering and sometimes from the arts and sciences too. One thing palpable, after being subjected to this routine everyday, was I never got to know who my real seniors were, as I never encountered anyone from the EE department.

One Friday afternoon, just when I thought I could escape the prying eyes of seniors, my fast pace home was interrupted by two seniors. I knew this was going to be another of those long Friday afternoons. I gave them my SD (Self Definition/Sontha Dabba), which was a standard practice, and part of which said I joined the EE branch. From there this talk went into unchartered territory as they started asking me about Thevenin's theorem, Norton's theorem. This was very unlike the ragging I had encountered earlier where you are at times subjugated to phyiscal and mental humiliation. But this was turning out to be not one of those. This was one of the most interesting talk I had with anyone on the campus and probably in retrospect I could say that this was the start of a four year long endearing memories.

That talk in short says all about the EE department and its students. This department had earned a reputation of being rigid, stern and highly disciplined. This department had in its faculty, members like Prof. Ratnam, Prof. Govind Rao, Prof. Sitaramam, Prof. Ramamurthy and Dr. Bapi Raju to name a few. You could easily see the demarcation as to how the classes and labs were conducted and how the students of these department were. It says a lot about the institution that these people built. It rose above mediocrity (that is not to take away anything from the other departments), often times challenging the entire university apparatus. It takes a lot of courage to rise above the average and then make everyone else believe the same. It takes a lot of character to set higher standards and then follow them under all adversity. I am sure these Professors had endured a lot of flak while building the institution, at times from their peers and others from their very own students (and they still do). What I saw, during my four years there, must have been the result of years of unperturbed dedication.

Today, when I look back, I realize how fortunate I am, to have done my undergrad from that department. I feel very proud to say that I did my undergrad from the EE department of AU. It is no mere coincidence that this department within a span of two years had produced the GATE topper twice (one of whom is a very dear friend of mine) and one GATE second ranker (one of the two who ragged me and was probing my understanding about Thevenin's theorem). This is, again, not to take away anything from those rankers. They thoroughly and richly deserved it. It couldn't have happened to any more brilliant people, but I am sure they too would acknowledge the sleight of that wonderful faculty.

Alas, those achievements turned out to be just like an earthern lamp which when lit gives light all around, but then it also exudes its full brilliance right before it starts to wane down. On my last visit there, I could see first hand how the department had slipped down. We met some of the older faculty members who have since moved to private colleges. It was a sorry plight to see the once revered department being run by people who interpreted their seniors way of running it all wrong. While the Professors before them believed in always setting the bar high up, with emphasis always on attaining higher learning (transient state to steady state by Prof Govind Rao), exploring beyond the realm of text books (any of Prof Ratnam's lectures). They sometimes seemed a bit stretched, especially, when you saw themselves in the context of students from other departments. We had been asked to leave 7 lab's at a stretch when we couldn't answer a seemingly innocous question What is voltage rise ? , or were made to look like idiot savant's for not knowing the meaning of moron :-). I am sure much of this was intended to get us out of our shells and to disband any preconceived notions we might have had about how our next 4 years would be like. Unfortunately, the part which caught on with the junior professors, readers and lecturers was the nagging part. They just thought that they could have their way and keep us under leash by always keeping us on our toes. This was a classic case of Lost in Transition. One group of people were looking to liberate us and the other trying to restrain us.

Today, AU is being considered for conversion from a University to an IIT, a rare honor for any Indian university. How I wish, the UGC could have woken up atleast 5-8 years earlier, that is when they would have seen this department (I cannot speak for the university) in its full splendor. Even today, if I still haven't forgotten some of the lectures, terms, and the process which I had learnt there, it is because of the quality of teaching. I am not sure how different IIT's mode of teaching is, but I am sure they too would have admired the EE department of AU and would not have found it wanting in any respect.

How happy they will be in seeing the institute graduate from a BE to BTech. It would have been a fitting ode to the distinguished faculty to have seen their hardwork, dedication, vision pay off this way. But then they didn't work for this honor right, because no work can be as resplendent as this when driven by the fruit. The fruit should always be the by product of karma, not the guiding light.

Sunday, November 06, 2005

Strange Loops

Strange loops occurs whenever, by moving (up/down), through the levels of some hierarchial system, we unexpectedly find ourselves right back where we started. Sometimes I use the term Tangled Hierarchy to describe a system in which a Strange Loop occurs.

Hofstadter is talking about one of the types of recursion here. Recursion, that eternal principle which is the core of all programming. I don't think its pure coincidence that it rears its head at all times at the most unknown places.

It, being a common tenet for all programming, is because recursion is present all around us. Its the basis for mathematics, sciences and life as a whole.


I, for one, believe that the universe is a manifestation of a small pattern repeated over and over again by using recursion principle. (More on this later ...)

Whenever we encounter recursion, we always look for a terminating condition to break out of the loop:

while(true)
{
TryAgain();

if(M)
{
break;
}
}

In the above psuedo-code we break out of recursion when M is achieved. This can be achieved while we go through this another loop TryAgain which at some point will break you free of the loop.

But as we will see later on there is more than one way to break out of the loop even without achieving M here ...

The strange loop which Hofstadter is talking about is when you are in a circular loop. People familiar with a circular linked list can easily identify with it. Its a hierarchy with a parent node showing way to a child node. But somewhere along, while traversing the hierarchy, the child node loops back to one of its parent nodes and we end up in a tangled hierarchy.