 |
del.icio.us |
 |
Digg |
 |
Furl |
 |
|
 |
Rojo |
| Add to OnlyWire |
In mathematics and computer science, Zeno machines (abbreviated ZM, and also called Accelerated Turing machine, ACM) are a hypothetical computational model related to Turing machines that allows a countably infinite number of algorithmic steps to be performed in finite time. These machines are ruled out in most models of computation.
More formally, a Zeno machine is a Turing machine that takes 2-n units of time to perform its n-th step; thus, the first step takes 0.5 units of time, the second takes 0.25, the third 0.125 and so on, so that after one unit of time, an infinite number of steps will have been performed.
The idea of Zeno machines was first discussed by Hermann Weyl in 1927; they are named after the ancient Greek philosopher Zeno of Elea.
Contents |
Zeno machines and computability
Zeno machines allow some functions to be computed that are not Turing-computable. For example, the halting problem for Turing machines can easily be solved by a Zeno machine (using the following pseudocode algorithm):
begin program
write 0 on the first position of the output tape;
set i = 1;
begin loop
simulate the first i steps of the given Turing machine on the given input;
if the Turing machine has halted, then write 1 on the first position of the output tape;
i = i + 1;
end loop
end program
Computing of this kind that goes beyond the Turing Limit is called hypercomputation. It is also an example of a supertask.
Are Zeno machines physically possible?
Some people claim that while Zeno machines are an interesting mathematical concept, they cannot be physically realized. One argument for this position is that because the operations need to be performed exponentially faster, sooner or later certain physical components would need to move faster than the speed of light, which is physically impossible.
Are Zeno machines logically possible?
Other people claim that Zeno machines aren't even logically coherent. For example, consider a Zeno machine that continues to alternatively write different outputs, or a Zeno machine that will keep moving its writehead to the left, regardless of what symbols are on the tape. It seems clear that these machines will never stop, but the possibility of Zeno machines suggests that after a certain amount of time, the Zeno machine is done, as it will have completed the countably infinite number of operations that such a machine would take. Hence, some people claim that the possibility of Zeno machines leads to a logical contradiction, thus making Zeno machines logically impossible. Indeed, some people regard the logical impossibility of Zeno machines as just another instance of the logical impossibility of supertasks in general, other examples of which include Zeno's paradox, Thomson's lamp, and the Balls and vase problem.
See also
References
- Petrus H. Potgieter, Zeno machines and hypercomputation, 2004, http://arxiv.org/abs/cs/0412022
