(Read part – 1 before reading this)

What still remains interesting is to get rid of this weird looking function and replace it with something purely mathematical. In a purely mathematical scenario, we cannot get any help from global variables, so a and r are out of question.

So, let’s say there is a function f that describes what we are doing inside HowLong(), ie, a function that takes as its input the current value of HowLong() and returns something larger than it. So in the first case, f(x) = x + 4. The second case, however, cannot be modeled by f. Now, let’s use the notation f[n](x) to denote f acted n times on x. So f[2](x) is f(f(x)). f[0](x) = x and so on. Notice that our friend HowLong() is now f[infinity](x).

Using the above notation, what we are looking for is a function f such that f[n](x) > f[n – 1](x) for all n and x and f[infinity](x) is finite. This, as it turns out, is an interesting and non-trivial exercise. You may want to try it yourself.

A possible function that satisfies the above properties is this –

f(x) = (x + [x + 1]) / 2

where [x] means the smallest integer larger than x.

All it does is to take the point x half-way closer to [x + 1], ie, the next integer. So each time you apply f, you go halfway closer to the next integer and hence reach the integer – a finite value – after an infinite number of iterations.

This function is still not that cute. The ultimate mathematical triumph will be to be able to write f(x) without using such complicated functions like the integer value function. Does anybody have an idea?

Note – A lot of the material above was developed during discussions with Robin Kothari and Nitin Basant (independently) Also, if you find a flaw in the post, please point it out.

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.