# Zeno machine

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 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 2n 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, a countably infinite (i.e. 0) number of steps will have been performed.

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.

## 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;
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
```

Computing of this kind that goes beyond the Turing Limit is called hypercomputation. It is also an example of a supertask.

Also, the halting problem for Zeno machines is not solvable by a Zeno machine (Potgieter, 2006).