nach oben

Natural Computing

Erschienen in:

01.09.2009

Abstract geometrical computation 3: black holes for classical and analog computing

verfasst von: Jérôme Durand-Lose

Erschienen in: Natural Computing | Ausgabe 3/2009

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

The so-called Black Hole model of computation involves a non Euclidean space-time where one device is infinitely “accelerated” on one world-line but can send some limited information to an observer working at “normal pace”. The key stone is that after a finite duration, the observer has received the information or knows that no information was ever sent by the device which had an infinite time to complete its computation. This allows to decide semi-decidable problems and clearly falls out of classical computability. A setting in a continuous Euclidean space-time that mimics this is presented. Not only is Zeno effect possible but it is used to unleash the black hole power. Both discrete (classical) computation and analog computation (in the understanding of Blum, Shub and Smale) are considered. Moreover, using nested singularities (which are built), it is shown how to decide higher levels of the corresponding arithmetical hierarchies.

Vorheriger Artikel Quantum complementarity and logical indeterminacy

Nächster Artikel Information processing with structured excitable medium

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

Throughout the article location is to be understood as a position in space and time and position as only spatial.

This is why we do not talk about any analytic hierarchy.

For example think about the so-called blue-shift effect and how it might be countered (Németi and Dávid 2006, Sub. 5.3.1).

Blum L, Shub M, Smale S (1989) On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines. Bull Am Math Soc 21(1): 1–46MATHCrossRefMathSciNet

Blum L, Cucker F, Shub M, Smale S (1998) Complexity and real computation. Springer, New York

Bournez O (1999a) Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy. Theor Comp Sci 210(1): 21–71MATHCrossRefMathSciNet

Bournez O (1999b) Some bounds on the computational power of piecewise constant derivative systems. Theory Comput Syst 32(1):35–67MATHCrossRefMathSciNet

Bournez O, Emmanuel H (2007) On the computational capabilities of several models. In: Durand-Lose J, Margenstern M (eds) Machines, Computations, and Universality, MCU ’07, volume 4664 of LNCS. Springer, pp 12–23

Chadzelek T, Hotz G (1999) Analytic machines. Theor Comp Sci 219(1–2):151–167MATHCrossRefMathSciNet

Copeland JB (2002) Hypercomputation. Minds Mach 12(4):461–502MATHCrossRef

Durand-Lose J (2006a) Abstract geometrical computation 1: embedding black hole computations with rational numbers. Fundam Inform 74(4):491–510MATHMathSciNet

Durand-Lose J (2006b) Forcasting black holes in abstract geometrical computation is highly unpredictable. In: Cai J-Y, Cooper SB, Li A (eds) Theory and applications of models of computations (TAMC ’06), number 3959 in LNCS. Springer, pp 644–653

Durand-Lose J (2007) Abstract geometrical computation and the linear Blum, Shub and Smale model. In: Cooper SB, Löwe B, Sorbi A (eds) Computation and logic in the real world, 3rd Conference on Computability in Europe (CiE ’07), number 4497 in LNCS. Springer, pp 238–247

Durand-Lose J (2008a) Abstract geometrical computation with accumulations: beyond the Blum, Shub and Smale model. In: Beckmann A, Dimitracopoulos C, Löwe B (eds) Logic and theory of algorithms, CiE 2008 (abstracts and extended abstracts of unpublished papers). University of Athens, pp 107–116

Durand-Lose J (2008b) The signal point of view: from cellular automata to signal machines. In: Durand B (ed) Journées automates cellulaires (JAC ’08), pp 238–249. URL http://www.lif.univ-mrs.fr/jac/

Etesi G, Németi I (2002) Non-Turing computations via Malament-Hogarth space-times. Int J Theor Phys 41(2):341–370 gr-qc/0104023

Hamkins JD (2002) Infinite time Turing machines: supertask computation. Minds Mach, 12(4):521–539 arXiv:math.LO/0212047

Hamkins JD (2007) A survey of infinite time Turing machines. In: Durand-Lose J, Margenstern M (eds) Machines, Computations and Universality (MCU ’07), number 4664 in LNCS. Springer, pp 62–71

Hamkins JD, Lewis A (2000) Infinite time Turing machines. J Symb Log 65(2):567–604. arXiv:math.LO/9808093

Hogarth ML (1994) Non-Turing computers and non-Turing computability. In: Biennial Meeting of the Philosophy of Science Association, pp 126–138

Hogarth ML (2004) Deciding arithmetic using SAD computers. Br J Philos Sci 55:681–691MATHCrossRefMathSciNet

Huckenbeck U (1989) Euclidian geometry in terms of automata theory. Theor Comp Sci 68(1):71–87MATHCrossRefMathSciNet

Huckenbeck U (1991) A result about the power of geometric oracle machines. Theor Comp Sci 88(2):231–251MATHCrossRefMathSciNet

Jacopini G, Sontacchi G (1990) Reversible parallel computation: an evolving space-model. Theor Comp Sci 73(1):1–46MATHCrossRefMathSciNet

Kawamura A (2005) Type-2 computability and Moore’s recursive functions. Electr Notes Theor Comput Sci 120:83–95CrossRefMathSciNet

Mycka J (2003a) Infinite limits and \({\mathbb{R}}\) -recursive functions. Acta Cybern 16(1):83–91MATHMathSciNet

Mycka J (2003b) μ-recursion and infinite limits. Theor Comp Sci 302(1–3):123–133MATHCrossRefMathSciNet

Mycka J (2006) Analog computation beyond the Turing limit. Appl Math Comput 178(1):103–117MATHCrossRefMathSciNet

Mycka J, Costa JF (2007) A new conceptual framework for analog computation. Theor Comp Sci 374(1–3):277–290MATHCrossRefMathSciNet

Naughton TJ, Woods D (2001) On the computational power of a continuous-space optical model of computation. In: Margenstern M (ed) Machines, Computations, and Universality (MCU ’01), volume 2055 of LNCS, pp 288–299

Németi I, Andréka H (2006) Can general relativistic computers break the Turing barrier? In: Beckmann A, Berger U, Löwe B, Tucker JV (eds) Logical approaches to computational barriers, 2nd Conference on Computability in Europe, CiE ’06, volume 3988 of LNCS. Springer, pp 398–412

Németi I, Dávid G (2006) Relativistic computers and the Turing barrier. Appl Math Comput 178(1):118–142MATHCrossRefMathSciNet

Weihrauch K (2000) Introduction to computable analysis. Texts in Theoretical computer science. Springer, Berlin

Welch PD (2008) The extentent of computation in malament-hogarth spacetime. Br J Philos Sci 59(4):659–674. doi:10.1093/bjps/axn031 MATHCrossRef

Ziegler M (2007) (Short) Survey of real hypercomputation. In: Barry Cooper S, Löwe B, Sorbi A (eds) Computation and logic in the real world, 3rd Conference on Computability in Europe, CiE ’07. volume 4497 of LNCS. Springer, pp 809–824

Titel: Abstract geometrical computation 3: black holes for classical and analog computing
verfasst von: Jérôme Durand-Lose
Publikationsdatum: 01.09.2009
Verlag: Springer Netherlands
Erschienen in: Natural Computing / Ausgabe 3/2009
Print ISSN: 1567-7818
Elektronische ISSN: 1572-9796
DOI: https://doi.org/10.1007/s11047-009-9117-0

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Weitere Artikel der Ausgabe 3/2009

On codeword design in metric DNA spaces

The computational status of physics

A new problem for rule following

Foundations of r-contiguous matching in negative selection for anomaly detection

Error suppression mechanisms for DNA tile self-assembly and their simulation

From reaction-diffusion to Physarum computing

Premium Partner