Infinite calculations in finite time

Problem Detail: 

This is probably a silly thought, but suppose we have a computer that's programmed to perform an infinite sequence of calculations and suppose the $i^\text{th}$ calculation takes $1/2^i$ seconds to complete. Then this computer can do an infinite number of calculations in a finite amount of time.

Why is this impossible? Is there a lower bound on how long it takes to carry out a non-trivial calculation?

Asked By : dsaxton

Answered By : Theory of Everything

This "kind" of computer is known as a Zeno Machine. Its computational model falls into a category called Hypercomputation. Hypercomputational models are mathematical abstractions, and because of the ways in which they are defined to work, they aren't physically possible.

Take your Zeno Machine for example. If we imagine the Zeno Machine to be a calculating machine of any kind, whether it uses an abacus or integrated circuit doesn't matter. Say the program data used by the machine is fed to it by an infinitely long tape of symbols (just like a Turing Machine).

Of course, we know from mathematics that:

$\frac{1}{2}+\frac{1}{4}+\frac{1}{8}... = \sum_{n=1}^{\infty}(\frac{1}{2})^n $

which we say is equal to $1$. Thus the computation should complete in 1 second because the sum absolutely converges.

But this convergence is, of course, dependent on $n$ going to (and reaching) infinity. In the physical sense, this means that as the time required for each calculation gets smaller, the "read head" of the calculating machine will have to zip along the symbols in the tape faster and faster. At some point, this speed will exceed the speed of light.

So answering your second question, the absolute lowest-possible bound on a calculation would probably be on the order of the Planck time, given the speed of light as the primary limiting factor in theoretical, but physically-plausible models of computation.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/47153