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

• 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

  Article  MATH  MathSciNet  Google Scholar 

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

  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

• 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–167

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  Google Scholar 

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

  MATH  MathSciNet  Google Scholar 

• 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

  Google Scholar 

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

  Google Scholar 

• 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

  Google Scholar 

• 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–691

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MathSciNet  Google Scholar 

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

  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

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

  Article  MATH  MathSciNet  Google Scholar 

• 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–142

  Article  MATH  MathSciNet  Google Scholar 

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

  Google Scholar 

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

  Article  MATH  Google Scholar 

• 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

Download references