In mathematics and computer science, the Zeno Machine (sometimes abbreviated to PM , also called the accelerated Turing machine ) is a hypothetical computer model associated with the Turing machine that can perform a countable number of algorithmic steps in a finite time. In most models of calculations, such machines are not considered.
More strictly, the Zeno machine is such a Turing machine, which requires 2 - n time units to complete the nth step. Thus, the first step requires 0.5 units of time, the second - 0.25, the third - 0.125, and so on, so that an infinite number of steps are performed per unit of time.
The idea of the Zeno machine was first discussed by Hermann Weil in 1927. It was named after the aporia of the ancient Greek philosopher Zeno of Elea . Such machines play a key role in some theories. For example, the Omega point theory developed by Frank Tippler is true only if the Zeno machine can exist.
Zeno's machine and computability
Some functions that cannot be computed on a Turing machine can be computed using the Zeno machine. For example, it can solve the problem of stopping (as illustrated by the following pseudocode ):
the beginning of the program
write 0 to the first cell on the tape;
cycle start
to simulate the next step of the work of this Turing machine at this entrance;
if the Turing machine stopped, then write 1 to the first cell on the tape and interrupt the cycle ;
end of cycle
end of the program
Such calculations that go beyond the capabilities of the Turing machine are called hypercomputation .
It is worth noting that the stopping problem for the Zeno machine itself cannot be solved on the Zeno machine (Potgieter, 2006).
See also
- Zeno's paradox
- Hypercomputations
- Lamp topson
- The problem of balls and vases
- Omega Point
Links
- Petrus H. Potgieter , Zeno machines and hypercomputation , 2006.