On Hofstadter’s Law (Part – 1)

In case you don’t already know it, the law says this –

It always takes longer than you expect, even when you take into account Hofstadter’s Law.

The interpretation, as you would have figured out already, has a tinge of recursion in it, just like most of the things associated with Hofstadter. All it says is that it always takes really long, but says that in a queer and humorous way. It is interesting however, to investigate the following question – “How long exactly?”

A first look at the law suggests that the answer would be “infinitely long”. For, let’s say, some reasoning leads us into believing that it is going to take n days. The reasoning might or might not involve Hofstadter’s Law. In either case, however, the law says that it will take more than n days. Even if we update our expectation and assume that it will take, say, n + 4 days, the law is still applicable to it because this time the reasoning that led us to the result involved the use of Hofstadter’s Law, a case which is taken care of in the law.

But does it necessarily mean that it will take infinitely long? That it may not, is what appears to be a possibility if we consider Zeno’s paradox. A brief description of the paradox follows –

Suppose you are racing a tortoise. You run at a speed of 10 km/hr and the tortoise runs at 1 km/hr. Initially, the tortoise is 1 meter ahead of you. Experience says, you will win. But consider the following reasoning. Let’s say the tortoise is at point A initially. After some time, you reach point A. But when you are at point A, the tortoise is a little ahead of you, say, at point B. You run a little more and reach B in some time. However, when this happens, the tortoise is still ahead of you. So you will keep doing this till eternity – running to the point where the tortoise currently is and then realizing that the tortoise is still a little ahead of you – and hence never catch the tortoise.

The reasoning is wrong, though not in a very obvious way. The flaw in it is that the thing that is infinite is the number of steps (one step being the process of going to the point where the tortoise currently is, for example, going from A to B is the second step) you take in catching the tortoise. The time you take, however, is not. That such a thing is possible, should not be a surprise to you if you have read things like convergence of series in your high school. A simple example is a Geometric Progression with a common ratio less than 1. In fact, it is not difficult to realize that the time taken by you in each step in the above paradox forms a Geometric Progression with common ratio less than 1.

What is the similarity between Zeno’s paradox and Hofstadter’s Law? Just like Zeno’s paradox, the thing that appears to be infinite in case of Hofstadter’s Law, is the number of times you make an increment in your expectation. This does not necessarily mean that the expectation, and hence the time taken (it takes longer than you expect, remember?) is infinite. So is our initial question answered? Not satisfactorily. We just know that it “might” take less than an infinite amount of time. We want to get into the details even further. We want to find out what “kinds” of time it can take. Can it, for example, take 2 days? How about 1 microsecond? Is there a lower bound on it? These (and several other arbitrary kinds) are the kinds of questions we wish to answer. So let’s get our hands dirty.

The essence of the law can be captured in the following simple recursive function –

HowLong() {

return something larger than HowLong();

}

The way we choose to return something larger than HowLong() is what’s going to decide the value returned by the function. For example, the function

HowLong() {

return HowLong() + 4;

}

will return infinity.

And the function

a = 1;

r = 2;

HowLong() {

a = a / r;

return HowLong() + a;

}

will return 1.

In fact, by taking suitable values for a and r, we can make the function return anything we want to. This answers one of our questions. There is no lower bound on the kinds of values our function can return, or indeed, on the kinds of times it can take according to Hofstadter’s Law.

Advertisements

3 thoughts on “On Hofstadter’s Law (Part – 1)

  1. Shouldn’t global variables be disallowed? Since that means that the expectation is more than the current value, by an amount which does not depend entirely on the current value.

  2. Vinayak says:

    Indeed. The global variable example was given just to show some motivation behind formulating a mathematical function. It is the immediate next step to realizing the connection with infinite geometric series. At least it was the immediate next step in my reasoning process.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s