| 词条 | Zeno machine |
| 释义 |
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, a countably infinite (i.e. ℵ0) number of steps will have been performed. The idea of Zeno machines was first discussed by Hermann Weyl in 1927; the name refers to Zeno's paradoxes, attributed to 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. Zeno machines and computabilityZeno machines would allow some functions to be computed that are not Turing-computable. For example, the halting problem for Turing machines can 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, in this case hypercomputation through a supertask - see there for further discussion and literature. See also
4 : Models of computation|Turing machine|Hypercomputation|Supertasks |
| 随便看 |
|
开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。