Nonuniversality explained. Issue 3 (3rd May 2016)

• Record Type: Journal Article
• Authors: Akl, Selim G.
• Is Part Of: International journal of parallel, emergent and distributed systems. Volume 31:Issue 3(2016)
• Page Start: 201
• Page End: 219
• Publication Date: 2016-05-03
• Subjects: Nonuniversality in computation -- simulation -- models of computation -- inherently parallel computations -- Church–Turing thesis -- Gödel's incompleteness theorem -- quantum computing; Parallel computers -- Periodicals; Electronic data processing -- Distributed processing -- Periodicals; Computer algorithms -- Periodicals; 004.35
• DOI: 10.1080/17445760.2015.1079321
• Languages: English
• ISSNs: 1744-5760

Abstract

Abstract : 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 can be simulated, more or less efficiently, on any other general-purpose computer . 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.