×

Abstract geometrical computation. III: Black holes for classical and analog computing. (English) Zbl 1192.68275

Summary: 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.
For Part I of this series of papers see [Zbl 1117.03043].

MSC:

68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68Q05 Models of computation (Turing machines, etc.) (MSC2010)

Citations:

Zbl 1117.03043
PDFBibTeX XMLCite
Full Text: DOI

References:

[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–46 · Zbl 0681.03020 · doi:10.1090/S0273-0979-1989-15750-9
[2] Blum L, Cucker F, Shub M, Smale S (1998) Complexity and real computation. Springer, New York · Zbl 0872.68036
[3] Bournez O (1999a) Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy. Theor Comp Sci 210(1): 21–71 · Zbl 0912.68032 · doi:10.1016/S0304-3975(98)00096-6
[4] Bournez O (1999b) Some bounds on the computational power of piecewise constant derivative systems. Theory Comput Syst 32(1):35–67 · Zbl 0914.68071 · doi:10.1007/s002240000111
[5] 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 · Zbl 1211.68196
[6] Chadzelek T, Hotz G (1999) Analytic machines. Theor Comp Sci 219(1–2):151–167 · Zbl 0916.68040 · doi:10.1016/S0304-3975(98)00287-4
[7] Copeland JB (2002) Hypercomputation. Minds Mach 12(4):461–502 · Zbl 1036.68058 · doi:10.1023/A:1021105915386
[8] Durand-Lose J (2006a) Abstract geometrical computation 1: embedding black hole computations with rational numbers. Fundam Inform 74(4):491–510 · Zbl 1117.03043
[9] 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 · Zbl 1117.03045
[10] 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 · Zbl 1151.68408
[11] 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
[12] 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/
[13] 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 · Zbl 0991.83030
[14] Hamkins JD (2002) Infinite time Turing machines: supertask computation. Minds Mach, 12(4):521–539 arXiv:math.LO/0212047 · Zbl 1030.68036
[15] 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 · Zbl 1211.03060
[16] Hamkins JD, Lewis A (2000) Infinite time Turing machines. J Symb Log 65(2):567–604. arXiv:math.LO/9808093 · Zbl 0963.03064
[17] Hogarth ML (1994) Non-Turing computers and non-Turing computability. In: Biennial Meeting of the Philosophy of Science Association, pp 126–138
[18] Hogarth ML (2004) Deciding arithmetic using SAD computers. Br J Philos Sci 55:681–691 · Zbl 1076.03027 · doi:10.1093/bjps/55.4.681
[19] Huckenbeck U (1989) Euclidian geometry in terms of automata theory. Theor Comp Sci 68(1):71–87 · Zbl 0678.68055 · doi:10.1016/0304-3975(89)90120-5
[20] Huckenbeck U (1991) A result about the power of geometric oracle machines. Theor Comp Sci 88(2):231–251 · Zbl 0742.51018 · doi:10.1016/0304-3975(91)90375-C
[21] Jacopini G, Sontacchi G (1990) Reversible parallel computation: an evolving space-model. Theor Comp Sci 73(1):1–46 · Zbl 0694.68040 · doi:10.1016/0304-3975(90)90160-J
[22] Kawamura A (2005) Type-2 computability and Moore’s recursive functions. Electr Notes Theor Comput Sci 120:83–95 · doi:10.1016/j.entcs.2004.06.036
[23] Mycka J (2003a) Infinite limits and \({\mathbb{R}}\) -recursive functions. Acta Cybern 16(1):83–91 · Zbl 1027.03034
[24] Mycka J (2003b) {\(\mu\)}-recursion and infinite limits. Theor Comp Sci 302(1–3):123–133 · Zbl 1044.68056 · doi:10.1016/S0304-3975(02)00744-2
[25] Mycka J (2006) Analog computation beyond the Turing limit. Appl Math Comput 178(1):103–117 · Zbl 1110.68045 · doi:10.1016/j.amc.2005.09.074
[26] Mycka J, Costa JF (2007) A new conceptual framework for analog computation. Theor Comp Sci 374(1–3):277–290 · Zbl 1164.68005 · doi:10.1016/j.tcs.2007.01.005
[27] 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 · Zbl 0984.68507
[28] 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 · Zbl 1145.68419
[29] Németi I, Dávid G (2006) Relativistic computers and the Turing barrier. Appl Math Comput 178(1):118–142 · Zbl 1104.68048 · doi:10.1016/j.amc.2005.09.075
[30] Weihrauch K (2000) Introduction to computable analysis. Texts in Theoretical computer science. Springer, Berlin · Zbl 0956.68056
[31] Welch PD (2008) The extentent of computation in malament-hogarth spacetime. Br J Philos Sci 59(4):659–674. doi: 10.1093/bjps/axn031 · Zbl 1154.83301 · doi:10.1093/bjps/axn031
[32] 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 · Zbl 1151.68414
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.