A reductio ad absurdum argument is used to establish that a universal computer cannot exist. The proof uses a recursive process whereby an assumed universal computer attempting to simulate itself descends into an infi...
详细信息
A reductio ad absurdum argument is used to establish that a universal computer cannot exist. The proof uses a recursive process whereby an assumed universal computer attempting to simulate itself descends into an infinite regress. Appealing to a more powerful computer to do the simulation leads to the same unavoidable conclusion.
The nonuniversality in computation theorem (NCT) states that no computer capable of a finite and fixed number of basic operations per time unit can be universal. This result, obtained in 2005, disproves major prevaili...
详细信息
The nonuniversality in computation theorem (NCT) states that no computer capable of a finite and fixed number of basic operations per time unit can be universal. This result, obtained in 2005, disproves major prevailing dogmas in computer science, on the strength of several counterexamples that differ significantly from one another. Thus, the NCT shows that the Church-Turing thesis (CTT) is false: It is not true that the Turing Machine can execute any computation possible on any other computer. It also disproves the inflated CTT, whereby there exists a universal computer, that is, a physical device capable of carrying out any computation conceivable. At the heart of the NCT is a refutation of the simulation principle, which states that any computation possible on a general-purpose computer A can be simulated, more or less efficiently, on any other general-purpose computer B. While more than 10 years have now elapsed since the NCT was established, the result is still widely misunderstood. This state of affairs is due to a number of misconceptions about the nature of the counterexamples and the significance of the NCT. The purpose of this paper is to dispel these misconceptions and convey the simple, yet important idea that universality in computation cannot be achieved, except by a computer capable, each time unit, of an infinite number of basic operations executed in parallel.
We present a simple example that disproves the universality principle. Unlike previous counter-examples to computational universality, it does not rely on extraneous phenomena, such as the availability of input variab...
详细信息
We present a simple example that disproves the universality principle. Unlike previous counter-examples to computational universality, it does not rely on extraneous phenomena, such as the availability of input variables that are time varying, computational complexity that changes with time or order of execution, physical variables that interact with each other, uncertain deadlines, or mathematical conditions among the variables that must be obeyed throughout the computation. In the most basic case of the new example, all that is used is a single pre-existing global variable whose value is modified by the computation itself. In addition, our example offers a new dimension for separating the computable from the uncomputable, while illustrating the power of parallelism in computation.
暂无评论