A number of unconventional computational problems are described in which parallelism plays a fundamental role. These problems highlight two recently uncovered aspects of parallel computation: 1. There exist computatio...
详细信息
A number of unconventional computational problems are described in which parallelism plays a fundamental role. These problems highlight two recently uncovered aspects of parallel computation: 1. There exist computations for which the running time of a parallel algorithm, compared to that of the best sequential algorithm, shows a speedup that is superlinear in the number of processors used, a feat that was previously believed to be impossible. 2. There exist inherently parallel computations, that is, computations that can be carried successfully in parallel, but not sequentially. A surprising consequence of these discoveries is that the concept of universality in computation, long held as a basic truth, is in fact false.
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.
暂无评论