Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Advances in Unconventional ComputingNonuniversality in Computation: Fifteen Misconceptions Rectified

Advances in Unconventional Computing: Nonuniversality in Computation: Fifteen Misconceptions... [In January 2005 I showed that universality in computation cannot be achieved. Specifically, I exhibited a number of distinct counterexamples, each of which sufficing to demonstrate that no finite and fixed computer can be universal in the sense of being able to simulate successfully any computation that can be executed on any other computer. The number and diversity of the counterexamples attest to the general nature of the nonuniversality result. This not only put to rest the “Church–Turing Thesis”, byChurch–Turing Thesis (CTT) proving it to be a false conjecture, but also was seen to apply, in addition to the Turing MachineTuring machine, to all computational models, past, present, and future, conventional and unconventional. While ten years have now passed since nonuniversality in computationNonuniversality in computation was established, the result remains largely misunderstood. There appear to be at least two main reasons for this state of affairs. As often happens to new ideas, the nonuniversality result was confronted with a stubborn entrenchment in a preconceived, deeply held, and quasi-religious belief in the existence of a universal computer. ThisUniversal computer was exacerbated by a failure to read the literature that demonstrates why such a belief is unfounded. Behavior of this sort, sadly not uncommon in science, explains the enduring mirage of the universal computer. The purpose of this chapter is to rectify the most notorious misconceptions associated with nonuniversality in computation. These misconceptions were expressed to the author in personal communications, orally, by email, and in referee reports. Each misconception is quoted verbatim and a detailed response to it is provided. The chapter concludes by inviting the reader to take a computational challenge.] http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png

Advances in Unconventional ComputingNonuniversality in Computation: Fifteen Misconceptions Rectified

Part of the Emergence, Complexity and Computation Book Series (volume 22)
Editors: Adamatzky, Andrew
Akl, Selim G.
Advances in Unconventional Computing — Jul 19, 2016
Download PDF
29 pages

Loading next page...
 
/lp/springer-journals/advances-in-unconventional-computing-nonuniversality-in-computation-WJwWmBXrgD
Publisher
Springer International Publishing
Copyright
© Springer International Publishing Switzerland 2017
ISBN
978-3-319-33923-8
Pages
1 –30
DOI
10.1007/978-3-319-33924-5_1
Publisher site
See Chapter on Publisher Site

Abstract

[In January 2005 I showed that universality in computation cannot be achieved. Specifically, I exhibited a number of distinct counterexamples, each of which sufficing to demonstrate that no finite and fixed computer can be universal in the sense of being able to simulate successfully any computation that can be executed on any other computer. The number and diversity of the counterexamples attest to the general nature of the nonuniversality result. This not only put to rest the “Church–Turing Thesis”, byChurch–Turing Thesis (CTT) proving it to be a false conjecture, but also was seen to apply, in addition to the Turing MachineTuring machine, to all computational models, past, present, and future, conventional and unconventional. While ten years have now passed since nonuniversality in computationNonuniversality in computation was established, the result remains largely misunderstood. There appear to be at least two main reasons for this state of affairs. As often happens to new ideas, the nonuniversality result was confronted with a stubborn entrenchment in a preconceived, deeply held, and quasi-religious belief in the existence of a universal computer. ThisUniversal computer was exacerbated by a failure to read the literature that demonstrates why such a belief is unfounded. Behavior of this sort, sadly not uncommon in science, explains the enduring mirage of the universal computer. The purpose of this chapter is to rectify the most notorious misconceptions associated with nonuniversality in computation. These misconceptions were expressed to the author in personal communications, orally, by email, and in referee reports. Each misconception is quoted verbatim and a detailed response to it is provided. The chapter concludes by inviting the reader to take a computational challenge.]

Published: Jul 19, 2016

Keywords: Turing Machine; Computable Function; Elementary Operation; Computational Device; Real Time Interaction

There are no references for this article.