Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Minds and Machines
Erschienen in: Minds and Machines 3/2009

01.08.2009

A Brief Critique of Pure Hypercomputation

verfasst von: Paolo Cotogno

Erschienen in: Minds and Machines | Ausgabe 3/2009

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Hypercomputation—the hypothesis that Turing-incomputable objects can be computed through infinitary means—is ineffective, as the unsolvability of the halting problem for Turing machines depends just on the absence of a definite value for some paradoxical construction; nature and quantity of computing resources are immaterial. The assumption that the halting problem is solved by oracles of higher Turing degree amounts just to postulation; infinite-time oracles are not actually solving paradoxes, but simply assigning them conventional values. Special values for non-terminating processes are likewise irrelevant, since diagonalization can cover any amount of value assignments. This should not be construed as a restriction of computing power: Turing’s uncomputability is not a ‘barrier’ to be broken, but simply an effect of the expressive power of consistent programming systems.
Vorheriger Artikel The Survival of the Fittest and the Reign of the Most Robust: In Biology and Elsewhere
Nächster Artikel Semantic Dispositionalism, Idealization, and Ceteris Paribus Clauses

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
The hypothesis currently belongs to the field of non-conventional computation, but should be clearly distinguished from the approaches based on physical, chemical, or biological implementations of novel computing strategies; see Toffoli (1998) for an extensive introduction. Non-conventional computers may renounce the classical Von Neumann scheme, and explore alternative architectures; in general, they aim at overcoming some instance of intractability (e.g., see Sipser 2006, Chap. 9), without compromising with speculations on super-Turing computability.
 
2
For instance, relativistic hypercomputation, as theorized by Pitowsky, Hogarth, Németi, and others, faces substantial objections by Davis (2004), Silagadze (2005). Flaws in Kieu’s solution of Hilbert’s Tenth Problem through quantum adiabatic processes are discussed by Hagar and Korolev (2006), Smith (2006). The Calude-Pavlov approach to the solution of the Halting Problem through quantum measurement is criticized by Davis (2006). Objections to Xia’s Newtonian super-task can be found in Barrow (2005, Chap. 10).
 
3
The ‘conceptual’ treatment within category theory is not the only way of producing a unified account of diagonal theorems. A comparably high level of generality, and equivalent conclusions on the nature of uncomputability, has been eventually obtained also from the ‘formal’ viewpoint, initiated by Carnap’s remarks. A full elaboration can be found in Gaifman (2006).
 
4
Physical plausibility remains out of question. According to McLaughlin (1998), also the logical rejection of super-tasks could be vindicated, by renouncing standard theoretical approaches; Thomson’s lamp would turn out to be ‘dysfunctional’ on the grounds of internal set theory, a version of non-standard analysis.
 
5
Cooper (2006) admits the presence of this petitio principii, dubbing it ‘Davis’ Paradox’. Nevertheless, he appears confident that hypercomputation can be realized through ‘the set of all real numbers, within which the scientist commonly describes the material universe’. As we saw in Cotogno (2003), this is not the case: if computable reals are taken in approximated form, then they do not exceed the boundaries of the Church-Turing Thesis; otherwise, if taken in infinite precision, they assume the realization of super-tasks, and face the related objections.
 
6
As Wells (2004) reports, Tarski himself was implicitly entertaining the idea that classical definitions may involve some form of hypercomputational decidability. The discussion initiated by Wells has the potential of shedding new light on the relationship between classical and constructive foundations; we may consider it as the most interesting achievement of the hypercomputation area.
 
7
If one really intends to theorize computability without being vexed by diagonalization, renouncing bivalence is not enough: one should leave classical logic altogether, as done in the programme of synthetic computability, proposed by Bauer (2006). In this approach, all functions are assumed to be computable a priori, with no concern for algorithmic definitions, but logical principles are intuitionistic: diagonal uncomputability is, in a way, turned into a built-in feature.
 
Literatur
Akl, S. G., & Fraser, R. (2006). Accelerating machines. Technical Report 2006-510. Kingston, Ontario: Queen’s University.
Bailey, D. H., Borwein, P. B., & Plouffe, S. (1997). On the rapid computation of various polylogarithmic constants. Mathematics of Computation, 66, 903–913.MATHCrossRefMathSciNet
Barrow, J. D. (2005). The infinite book. London: Jonathan Cape.
Bauer, A. (2006). First steps in synthetic computability theory. Electronic Notes in Theoretical Computer Science, 155, 5–31.CrossRef
Benacerraf, P. (1962). Tasks, super-tasks, and the modern eleatics. The Journal of Philosophy, 59, 765–784.CrossRef
Cotogno, P. (2003). Hypercomputation and the physical Church-Turing thesis. The British Journal for the Philosophy of Science, 54, 181–223.MATHCrossRefMathSciNet
Cotogno, P. (2007). A note on Gödel’s theorem and the rejection of Hilbert’s programme. Poster Presented at the Gödel Centenary Symposium. University of Vienna.
Davis, M. (1982). Computability and unsolvability, (revised edition). New York: Dover.
Davis, M. (2004). The myth of hypercomputation. In C. Teuscher (Ed.), Alan turing: The life and legacy of a great thinker (pp. 195–212). Berlin: Springer.
Davis, M. (2006a). Computability, computation, and the real world. In S. Termini (Ed.), Imagination and rigor (pp. 63–70). Milan: Springer.CrossRef
Delong, H. (1970). A profile of mathematical logic. Reading: Addison-Wesley.MATH
Feferman, S. (1992). Turing’s “Oracle”: From absolute to relative computability—and back. In J. Echeverria, A. Ibarra, & T. Mormann (Eds.), The space of mathematics (pp. 314–348). Berlin: de Gruyter.
Gaifman, H. (2006). Naming and diagonalization, from Cantor to Gödel to Kleene. Logic Journal of the Interest Group in Pure and Applied Logic, 10, 709–728.MathSciNet
Gorn, S. (1961). The treatment of ambiguity and paradox in mechanical language, Air Force Office of Scientific Research TN-603-61. Philadelphia: University of Pennsylvania.
Hagar, A., & Korolev, A. (2006). Quantum hypercomputability? Minds and Machines, 16, 87–93.CrossRef
Kieu, T. D., & Ord, T. (2005). The diagonal method and hypercomputation. British Journal for the Philosophy of Science, 56, 147–156.MATHCrossRefMathSciNet
Kleene, S. C. (1974). Introduction to metamathematics. Amsterdam: North-Holland.
Lawvere, F. W. (1969). Diagonal arguments and cartesian closed categories. In P. Hilton (Ed.), Category theory, homology theory and their applications II (pp. 134–145). Berlin: Springer.CrossRef
Lawvere, F. W. (2006). Author commentary. Reprints in Theory and Applications of Categories, 15, 1–2.
Lawvere, F. W., & Schanuel, S. H. (2007). Conceptual mathematics: A first introduction to categories. Cambridge: Cambridge University Press.
Machtey, M., & Young, P. (1978). An introduction to the general theory of algorithms. New York: Elsevier.MATH
Pavlović, D. (1992). On the structure of paradoxes. Archives for Mathematical Logic, 31, 397–406.MATHCrossRef
Shagrir, O. (2004). Super-tasks, accelerating Turing machines and uncomputability. Theoretical Computer Science, 317, 105–114.MATHCrossRefMathSciNet
Silagadze, Z. (2005). Zeno and modern science. Acta Physica Polonica, B36, 2887–2930.
Sipser, M. (2006). Introduction to the theory of computation, (2nd ed). Boston: Thomson.
Smith, W. D. (2006). Three counterexamples refuting Kieu’s plan for “quantum adiabatic hypercomputation”, and some uncomputable quantum mechanical tasks. Applied Mathematics and Computation, 178, 184–193.MATHCrossRefMathSciNet
Soto-Andrade, J., & Varela, F. J. (1984). Self-reference and fixed points: A discussion and an extension of Lawvere’s theorem. Acta Applicandae Mathematicae, 2, 1–19.MATHCrossRefMathSciNet
Toffoli, T. (1998). Non-conventional computers. Encyclopedia of Electrical and Electronics Engineering, 14, 455–471. New York: Wiley.
Turing, A. M. (2004). Systems of logic based on ordinals. Proceedings of the London Mathematical Society 45, 161–228 (1939). Reprinted in B. J. Copeland (Ed.), The essential turing (pp. 125-204). Oxford: Oxford University Press.
Welch, P. D. (2004a). On the possibility, or otherwise, of hypercomputation. British Journal for the Philosophy of Science, 55, 739–746.MATHCrossRefMathSciNet
Welch, P. D. (2004b). Post’s and other problems in higher supertasks. In B. Löwe, B. Piwinger, & T. Räsch (Eds.), Foundations of the formal sciences III (pp. 223–237). Dordrecht: Kluwer.
Yanofsky, N. S. (2003). A universal approach to self-referential paradoxes, incompleteness and fixed points. Bulletin of Symbolic Logic, 9, 362–386.MATHCrossRefMathSciNet
Metadaten
Titel
A Brief Critique of Pure Hypercomputation
verfasst von
Paolo Cotogno
Publikationsdatum
01.08.2009
Verlag
Springer Netherlands
Erschienen in
Minds and Machines / Ausgabe 3/2009
Print ISSN: 0924-6495
Elektronische ISSN: 1572-8641
DOI
https://doi.org/10.1007/s11023-009-9161-7

Weitere Artikel der Ausgabe 3/2009

Minds and Machines 3/2009 Zur Ausgabe

OriginalPaper

A Challenge for Machine Ethics

OriginalPaper

The Survival of the Fittest and the Reign of the Most Robust: In Biology and Elsewhere

OriginalPaper

Where is Cognitive Science Heading?

OriginalPaper

Empathy with Inanimate Objects and the Uncanny Valley

BookReview

Michael Devitt, Ignorance of Language

OriginalPaper

Enaction-Based Artificial Intelligence: Toward Co-evolution with Humans in the Loop