This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Zeno machine" – news ·newspapers ·books ·scholar ·JSTOR(May 2021) (Learn how and when to remove this message)

Inmathematics andcomputer science,Zeno machines (abbreviatedZM, and also calledaccelerated Turing machine,ATM) are a hypothetical computational model related toTuring machines that are capable of carrying out computations involving acountably infinite number of algorithmic steps.^[1] These machines are ruled out in most models of computation.

The idea of Zeno machines was first discussed byHermann Weyl in 1927; the name refers toZeno's paradoxes, attributed to the ancient Greek philosopherZeno of Elea. Zeno machines play a crucial role in some theories. The theory of theOmega Point devised by physicistFrank 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. This can be thought of as asupertask where${\displaystyle \frac{1}{2^n}}$ units of time are taken to perform the${\displaystyle 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, acountably infinite number of steps will have been performed.

A more formal model of the Zeno machine is theinfinite time Turing machine. Defined first in unpublished work by Jeffrey Kidder and expanded upon by Joel Hamkins and Andy Lewis, inInfinite Time Turing Machines,^[2] the infinite time Turing machine is an extension of the classical Turing machine model, to includetransfinite time; that is time beyond all finite time.^[2] A classical Turing machine has a status at step${\displaystyle 0}$ (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. AnITTM maintains these properties, but also defines the status of the machine atlimit ordinals, that is ordinals that are neither${\displaystyle 0}$ nor the successor of any ordinal. The status of a Turing machine consists of 3 parts:

1. The state
2. The location of the read-write head
3. The contents of the tape

Just as a classical Turing machine has a labeled start state, which is the state at the start of a program, anITTM has a labeledlimit state which is the state for the machine at any limit ordinal.[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.^[1][2] Lastly the state of the tape is determined by thelimit supremum of previous tape states. For some machine${\displaystyle T}$, a cell${\displaystyle k}$ and, alimit ordinal${\displaystyle \lambda }$ then

${\displaystyle T(\lambda {)}_k=\underset{n\to \lambda }{lim sup}T(n{)}_k}$

That is the${\displaystyle k}$th cell at time${\displaystyle \lambda }$ is the limit supremum of that same cell as the machine approaches${\displaystyle \lambda }$.^[1] This can be thought of as the limit if it converges or${\displaystyle 1}$ otherwise.^[1]

Zeno machines have been proposed as a model of computation more powerful than classical Turing machines, based on their ability to solvethe halting problem for classical Turing machines.^[3] Cristian Calude and Ludwig Staiger present the followingpseudocode algorithm as a solution to the halting problem when run on a Zeno machine.^[4]

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 haltedthen            write 1 on the first position of the output tape and break out of loop;end loopend program

By inspecting the first position of the output tape after${\displaystyle 1}$ 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${\displaystyle [0,1)}$, and so it is impossible to inspect the tape at time${\displaystyle 1}$. 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.^[3]

Infinite time Turing machines however, are capable of implementing the given algorithm, halting at time${\displaystyle \omega }$ with the correct solution,^[2] since they do define their state for transfinite steps.^[3] All${\displaystyle {\mathrm{\Pi }}_1^1}$ sets aredecidable by infinite time Turing machines, and${\displaystyle {\mathrm{\Delta }}_2^1}$ sets aresemidecidable.^{[2][clarification needed]}

Zeno machines cannot solve their own halting problem.^[4]

• Computation in the limit
• Specker sequence
• Ross–Littlewood paradox

• Models of computation
• Turing machine
• Hypercomputation
• Supertasks

• Articles with short description
• Short description matches Wikidata
• Articles needing additional references from May 2021
• All articles needing additional references
• Wikipedia articles needing clarification from May 2021
• Articles with example pseudocode