Zeno machine

From Wikipedia, the free encyclopedia

In mathematics and computer science, Zeno machines (abbreviated ZM, and also called Accelerated Turing machine, ACM) are a hypothetical computational model related to Turing machines that allows a countably infinite number of algorithmic steps to be performed in finite time. These machines are ruled out in most models of computation.

More formally, a Zeno machine is a Turing machine that takes 2^-n units of time to perform its 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, an infinite number of steps will have been performed.

1 Origin of Zeno machines
2 Zeno machines and computability
3 See also
4 References

[edit] Origin of Zeno machines

The idea of Zeno machines was first discussed by Hermann Weyl in 1927; they are named after the ancient Greek philosopher Zeno.

[edit] 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;
  set i = 1;
  begin loop
    simulate the first i steps 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;
    i = i + 1;
  end loop
end program

(The halting problem for Zeno machines cannot be solved using a Zeno machine, however).

Unfortunately, though, the naive approach of Zeno machines to infinite calculations leads to problems. For example, unlike with a Turing machine, the output of a Zeno machine after it finishes its computation (i.e., after one time unit) need not be in a defined state; this can happen if the machine continues to alternatively write different outputs, for example. Other complications include undefined internal states of the machine, writeheads that "run away to infinity" and other such things.

The following pseudocode algorithm, which attempts to algorithmically determine whether the twin prime conjecture is true, illustrates this:

begin program
  set i = 3;
  begin loop
    write 0 on the first position of the output tape;
    if i and i + 2 are prime, then write 1 in the first position of the output tape;
    i = i + 2
  end loop
end program

If the twin prime conjecture does not hold, then the output of this Zeno machine will be 0; otherwise, however, the machine will continue to write out zeroes and ones alternatively, ad infinitum, causing the terminal state after one unit of running time to be undefined.

One might be tempted to remedy these problems by introducing a mechanism that exists these abnormalities and remedies them (by freezing the machine's output, moving the write head to a definite position and setting a special internal flag); however, doing so would essentially be the same as introducing an oracle for the very problem that one wishes to solve.