Zeno Machine - Zeno Machines and Computability

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).