Zeno machine
Encyclopedia
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 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.
The idea of Zeno machines was first discussed by Hermann Weyl
in 1927; they are named after the ancient Greek philosopher Zeno of Elea
. 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.
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).
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, Zeno machines (abbreviated ZM, and also called Accelerated Turing machine, ATM) 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.
The idea of Zeno machines was first discussed by Hermann Weyl
Hermann Weyl
Hermann Klaus Hugo Weyl was a German mathematician and theoretical physicist. Although much of his working life was spent in Zürich, Switzerland and then Princeton, he is associated with the University of Göttingen tradition of mathematics, represented by David Hilbert and Hermann Minkowski.His...
in 1927; they are named after the ancient Greek philosopher Zeno of Elea
Zeno of Elea
Zeno of Elea was a pre-Socratic Greek philosopher of southern Italy and a member of the Eleatic School founded by Parmenides. Aristotle called him the inventor of the dialectic. He is best known for his paradoxes, which Bertrand Russell has described as "immeasurably subtle and profound".- Life...
. Zeno machines play a crucial role in some theories. The theory of the Omega Point
Omega point
Omega Point is a term coined by the French Jesuit Pierre Teilhard de Chardin to describe a maximum level of complexity and consciousness towards which he believed the universe was evolving....
devised by physicist Frank J. Tipler
Frank J. Tipler
Frank Jennings Tipler is a mathematical physicist and cosmologist, holding a joint appointment in the Departments of Mathematics and Physics at Tulane University. Tipler has authored books and papers on the Omega Point, which he claims is a mechanism for the resurrection of the dead. It has been...
, for instance, can only be valid if zeno machines are possible.
Zeno machines and computability
Zeno machines allow some functions to be computed that are not Turing-computable. For example, the halting problemHalting problem
In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...
for Turing machines can easily be solved by a Zeno machine (using the following pseudocode
Pseudocode
In computer science and numerical computation, pseudocode is a compact and informal high-level description of the operating principle of a computer program or other algorithm. It uses the structural conventions of a programming language, but is intended for human reading rather than machine reading...
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
Hypercomputation
Hypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
. It is also an example of a supertask
Supertask
In philosophy, a supertask is a quantifiably infinite number of operations that occur sequentially within a finite interval of time. Supertasks are called "hypertasks" when the number of operations becomes innumerably infinite. The term supertask was coined by the philosopher James F...
.
Also, the halting problem for Zeno machines is not solvable by a Zeno machine (Potgieter, 2006).
See also
- Zeno's paradoxesZeno's paradoxesZeno's paradoxes are a set of problems generally thought to have been devised by Greek philosopher Zeno of Elea to support Parmenides's doctrine that "all is one" and that, contrary to the evidence of our senses, the belief in plurality and change is mistaken, and in particular that motion is...
- HypercomputationHypercomputationHypercomputation or super-Turing computation refers to models of computation that are more powerful than, or are incomparable with, Turing computability. This includes various hypothetical methods for the computation of non-Turing-computable functions, following super-recursive algorithms...
- SupertaskSupertaskIn philosophy, a supertask is a quantifiably infinite number of operations that occur sequentially within a finite interval of time. Supertasks are called "hypertasks" when the number of operations becomes innumerably infinite. The term supertask was coined by the philosopher James F...
- Thomson's lampThomson's lampThomson's lamp is a puzzle that is a variation on Zeno's paradoxes. It was devised by philosopher James F. Thomson, who also coined the term supertask....
- Ross-Littlewood paradox
- Tipler's Omega Point