On Hofstadter’s Law (Part – 2)

(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.