## Sunday, June 18, 2006

Avatars of the Tortoise
or
Circular reasoning

Jorge Luis Borges liked old metaphors. The older the better. One of the characteristic forms of his essays was the following of a metaphor through history.
The archetypal example is "The Eternal Rose of Coleridge" which is self referential, because Borges compared excellent metaphors to that Rose ("The Name of" which is the title of a best seller).

I was struck by "Avatars of the Tortoise," well actually appalled. Borges considers many versions of Zeno's paradox. Zeno said consider the fleet Achilles who runs the hundred meters in 10 seconds, 10 times as fast as the slow tortoise (this has to be the worlds fastest tortoise). If he starts 100 meters behind the tortoise quickly reaches the point where the tortoise started, but the tortois is 10 meters ahead of him. He makes up that distance, but the tortoise is then 1 meters ahead of him. He makes up that distance but the tortoise is 10 centimeters ahead of him. The series goes on forever, therefore the fleet Achilles never passes the slow tortoise.

Zeno's error is obvious. "Never passes" means that there is an infinite interval of time before Achilles passes the tortoise. It is not necessarily true that the sum of an infinite series is infinite. In the example Achilles passes the tortoise after
11 and 1/9 seconds, that is 100/9 seconds since he starts 100 meters behind and gains 9 meters per second.

Amazingly the great Borges took Zeno's paradox seriously. He argues that it is a hint of unreality that convinces us that the image we have made of the universe is an illusion.

I think it shows that people find the concept of infinity very very confusing. In fact, I think that behind every profoundly counterintuitive result in mathematics you can find a tortoise. That they all have something to do with infinity.

This thought came back to me when I considered the mother of all counter-intuitive theorems Godel't theorem. Godel proved that, except for the simplest mathematical systems he called first order logic, it is not, in general, possible to determine whether an axiom system is consistent. That is we can not know if we can prove a contradiction from the axioms. The connection with infinity is clear. If we have looked and looked a billion years for a contradiction, we don't know if we would find it after a billion years and a day.

In a model universe which can only has a finite number of possible states, it is easy to check if axioms are consistent. Just see if they are true in any of the states. If they are, they are consistent. If they aren't they can't all be true in that universe, so they are inconsistent. That is, all is ok, if we consider only models with a finite state space.

Another case in which infinity makes infinite trouble is the halting problem. This is the question of whether a Turing machine will ever stop, that is, a question of whether a computer will ever finish running a program. We confront this problem whenever our system hangs. Thus windows users are much more knowledgeable about this fundamental issue than our Mac users. The problem is clearly related to Godel's problem, and, in fact, the questions are equivalent. It is easy to prove that no computer program can tell, for any other program, if a computer will ever stop if it is running the other program. The proof is take the program (A) which determines if another computer program will stop running. Rewrite A to B so that if A outputs "yes" add an infinite loop and if A outputs "no" B prints "no" and stops. Now use B as an input to B. If B stops, B doesn't stop. If B doesn't stop B stops. Now that is a paradox.

There is an analogous problem which can be solved. A Turing machine has an infinite memory. The memory is in two forms, one is the "state" of the Turing machine of which there are a finite number, the other is a tape with 0's an 1's written on it.

Now consider a finite circular tape with N bits of information. There is a Turing machine (C) which can tell if any other Turing machine will stop if set on a circular tape with N zeros. The reason is that there are only finitely many possible states of the tape and Turing machine. If the Turing machine moves around for a while and gets to a state (of it and the tape) where it has already been, it will never stop. Otherwise it will stop. C has to keep track of every state of the tape/turing machine and check it against every previous state.

In fact C can do this with another finite tape (with many many more than N bits of information but still finite).

The halting problem does not exist if we consider only Turing machines with finite circular tapes.

Now the question is might our universe have a finite state space ? Blake would disagree claiming one can hold infinity in a grain of sand and eternity in an hour, but Blake didn't know about Heisenberg. There is a smallest measurable interval of time and space. If the universe always has finite volume and lasts a finite period of time, it has a finite state space. That is, if the Universe is closed it is finite and all paradoxes are hints of reality that show that our images of the universe are as mistaken as Zeno.