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 are capable of carrying out computations involving a countably infinite number of algorithmic steps.

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.

A Zeno machine is a Turing machine that can take an infinite number of steps, and then continue take more steps.

[2] A classical Turing machine has a status at step

(in the start state, with an empty tape, read head at cell 0) and a procedure for getting from one status to the successive status.

In this way the status of a Turing machine is defined for all steps corresponding to a natural number.

[1] This is the case even if the machine has no other way to access this state, for example no node transitions to it.

The location of the read-write head is set to zero for at any limit step.

is the limit supremum of that same cell as the machine approaches

[1] Zeno machines have been proposed as a model of computation more powerful than classical Turing machines, based on their ability to solve the halting problem for classical Turing machines.

[3] Cristian Calude and Ludwig Staiger present the following pseudocode algorithm as a solution to the halting problem when run on a Zeno machine.

unit of time has elapsed we can determine whether the given Turing machine halts.

[4] In contrast Oron Shagrir argues that the state of a Zeno machine is only defined on the interval

Furthermore since classical Turing machines don't have any timing information, the addition of timing information whether accelerating or not does not itself add any computational power.

with the correct solution,[2] since they do define their state for transfinite steps.

sets are decidable by infinite time Turing machines, and

[2][clarification needed] Zeno machines cannot solve their own halting problem.