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 programComputing 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).
Read more about this topic: Zeno Machine
Famous quotes containing the word machines:
“The machines that are first invented to perform any particular movement are always the most complex, and succeeding artists generally discover that, with fewer wheels, with fewer principles of motion, than had originally been employed, the same effects may be more easily produced. The first systems, in the same manner, are always the most complex.”
—Adam Smith (1723–1790)