In mathematics and computer science, Zeno machines (abbreviated ZM, and also called accelerated Turing machine, ATM) are a hypothetical computational model related to Turing machines that are capable of carrying out computations involving a countably infinite number of algorithmic steps. These machines are ruled out in most models of computation.
The idea of Zeno machines was first discussed by Hermann Weyl in 1927; the name refers to Zeno's paradoxes, attributed to the ancient Greek philosopher Zeno of Elea. Zeno machines play a crucial role in some theories. The theory of the Omega Point devised by physicist Frank J. Tipler, for instance, can only be valid if Zeno machines are possible.
Definition
A Zeno machine is a Turing machine that can take an infinite number of steps, and then continue take more steps. This can be thought of as a supertask where <math>\frac{1}{2^n}</math> units of time are taken to perform the <math>n</math>-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, a countably infinite number of steps will have been performed.
Infinite time Turing machines
thumb|400px|right|class=skin-invert-image|An animation of an infinite time Turing machine based on the [[Thomson's lamp thought experiment. A cell alternates between <math>0</math> and <math>1</math> for steps before <math>\omega</math>. The cell becomes <math>1</math> at <math>\omega</math> since the sequence does not converge.]]
A more formal model of the Zeno machine is the infinite time Turing machine. Defined first in unpublished work by Jeffrey Kidder and expanded upon by Joel Hamkins and Andy Lewis, in Infinite Time Turing Machines, the infinite time Turing machine is an extension of the classical Turing machine model, to include transfinite time; that is time beyond all finite time. Cristian Calude and Ludwig Staiger present the following pseudocode algorithm as a solution to the halting problem when run on a Zeno machine.
begin program
write 0 on the first position of the output tape;
begin loop
simulate 1 successive step 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 and break out of loop;
end loop
end program
By inspecting the first position of the output tape after <math>1</math> unit of time has elapsed we can determine whether the given Turing machine halts.