Zeno machine

The Zeno machine referred to in the computability theory a fictional machine that can arbitrarily in finite time perform many computational steps. It represents an example of a performance beyond the Turing predictability . Following the Church-Turing thesis , this machine can in no way be implemented in practice.

The zeno machine is initially constructed like a Turing machine . It achieves its special performance by doubling the speed of its calculation in every step. So if it takes a minute for the first step, the second takes only 30 seconds, etc. According to the geometric sequence of the step durations, every calculation that requires a finite number of steps is done after two minutes.

Hermann Weyl first proposed zeno machines in 1927. Its name refers to similar paradoxes of Zeno of Elea .

Zeno machines and predictability

Zeno machines can realize some functions that cannot be calculated by Turing. For example, the holding problem for Turing machines can be solved with the following procedure:

Schreibe eine 0 auf die erste Position des Ausgabebands
Wiederhole in einer Schleife:
    Simuliere einen (weiteren) Schritt der auf dem Eingabeband gegebenen Turingmaschine
    Wenn die simulierte Turingmaschine angehalten hat, schreibe eine 1 auf die erste Position des Ausgabebands und beende die Schleife

As stated above, the result can be found on the output tape after two minutes.

The holding problem for zeno machines cannot be solved with zeno machines (Potgieter, 2006).

Applications

Beyond the theory of computability, the Zeno machine together with the Church-Turing thesis is always of interest when geometrically accelerated processes are assumed, e.g. B.

• the omega point according to de Chardin and Tipler
• In short, the law of accelerating utility

literature

• Petrus H. Potgieter: Zeno machines and hypercomputation . In: Theoretical Computer Science . 358, No. 1, July 31, 2006, pp. 23-33. doi : 10.1016 / j.tcs.2005.11.040 .