Look at the literature on Zeno machines / hypercomputation http://en.wikipedia.org/wiki/Zeno_machine

From: James Propp <jpropp@cs.uml.edu> To: math-fun@mailman.xmission.com

I wasn't able to attend Gathering for Gardner 9, but my student Linda Zayas-Palmer did, and she presented there a joint paper called "Carrying On with Infinite Decimals" (http://jamespropp.org/carrying.pdf); I'd be interested in people's comments (since at some point I plan to publish this in one of the Gathering for Gardner volumes).

One comment I've already received can be paraphrased as follows: "You describe these computations with infinite decimals as taking place in ordinary time, so that even though each individual digit eventually stabilizes, you have to wait till time omega to be able to read off the answer. Why not imagine a computer in which each carry in the 10^{-n} position takes 10^{-n} seconds, so that the computation finishes in finite time?"

I was wondering if anyone had seen any proposals for (unrealistic) models of computation along these lines.

One needs to take some care to make sure that the state of the system remains well-defined even at limit-times. For instance, if one switches a light switch on and off at times 1/2, 3/4, 7/8, ..., the state of the light at time 1 is undefined.

Still, it seems that even if one imposes constraints to avoid the aforementioned "light switch problem", one can get idealized computers of this kind to do all kinds of things ordinary computers can't do, such as solve the halting problem.

There must be existing literature on computers that can be made to run faster and faster.

Jim Propp

_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun