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.


2 comments:

ramakrishna u said...

SJ,
Thanks for the post. Nice one to begin with: recursion.

I have a few thoughts: the terms that we encounter in reasoning about programs: programs that are recursive and the terms that we encounter in the decidability theory, namely: recursively enumerable and recursive have their etymological roots in mathematics and logic. I donot rememer exactly who, but some logicians protested the use of the terms -- loosely as they called -- by computer scientists when referring to programs.

Also, we can reason about the termination of a recursive program iff the call is made on a provably (strictly) smaller problem. Of course, the reasoning whether a program will halt or not is the crux of the decidability theory, by Turing's halting problem.

Thanks!

sj said...

Even though I am no computer scientist, I am sure I would run into one of those logicians with my idea of recursion. But nevertheless, with a view of correcting myself, I would like to read the notes.

Also, we can reason about the termination of a recursive program iff the call is made on a provably (strictly) smaller problem. Of course, the reasoning whether a program will halt or not is the crux of the decidability theory, by Turing's halting problem.

You are exactly right and that is what GEB too does and we will reapproach this topic when we get to that chapter (it is chapters, if I am not wrong). I think Hofstadter makes a strong case by putting forth Godel's theorem, TNT, Turing's thorem to address decidability and/or termination.

The dictionary meaning of Recursion would term is as an expression obtained by repeating a pattern/principle/operation over and over again. As mathematicians, logicians and good part of humans, we don't like undecidability. (Not to digress, Eastern culture doesn't resent the unknown as much as Western culture does.)
Hence we always embed a terminating condition, which might not be the pristine recursion.