Abstract Geometrical Computation 1: Embedding Black Hole Computations with Rational Numbers

• Autorzy: Durand-Lose J.
• Języki publikacji: EN

Abstrakty

EN

The Black hole model of computation provides super-Turing computing power since it offers the possibility to decide in finite (observer's) time any recursively enumerable (R.E.) problem. In this paper, we provide a geometric model of computation, conservative abstract geometrical computation, that, although being based on rational numbers (and not real numbers), has the same property: it can simulate any Turing machine and can decide any R.E.problem through the creation of an accumulation. Finitely many signals can leave any accumulation, and it can be known whether anything leaves. This corresponds to a black hole effect.

Słowa kluczowe

EN

abstract geometrical computation; black hole model; energy conservation; Malament-Hogarth space-time; super-turing computation; turing universality; zeno phenomena

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 74, nr 4
• Strony: 491--510
• Opis fizyczny: bibliogr. 27 poz., wykr.

Twórcy

autor

Durand-Lose J.

• Laboratorie d'Informatique Fondamentale d'Orleans, Universite d'Orleans, B.P. 6759, F-45067 Orleans Cedex 2, France,

Bibliografia

• [1] Eugene Asarin and Oded Maler. Achilles and the Tortoise climbing up the arithmetical hierarchy. In FSTTCS '95, number 1026 in LNCS, pages 471-483, 1995.
• [2] Nino Boccara, J. Nasser, and M. Roger. Particle-like structures and interactions in spatio-temporal patterns generated by one-dimensional deterministic cellular automaton rules. Phys. Rev. A, 44(2):866-875, 1991.
• [3] Olivier Bournez. Achilles and the Tortoise climbing up the hyper-arithmetical hierarchy. Theoret. Comp. Sci., 210(1):21-71, 1999.
• [4] Jérôme Durand-Lose. Intrinsic universality of a 1-dimensional reversible cellular automaton. In STACS '97, number 1200 in LNCS, pages 439-450. Springer, 1997.
• [5] Jérôme Durand-Lose. Calculer géométriquement sur le plan - machines `a signaux. Habilitation `a diriger des recherches, ´Ecole Doctorale STIC, Université de Nice-Sophia Antipolis, 2003.
• [6] Jérôme Durand-Lose. Abstract geometrical computation for black hole computation (extended abstract). In M. Margenstern, editor, Universal Machines and Computations (MCU '04), number 3354 in LNCS, pages 175-186. Springer, 2005.
• [7] Marianne Delorme and Jacques Mazoyer. Signals on cellular automata. in [1], pp. 234-275, 2002.
• [8] Gabor Etesi and Istvan Nemeti. Non-Turing computations viaMalament-Hogarth space-times. Int. J. Theor. Phys., 41(2):341-370, 2002. gr-qc/0104023.
• [9] Eugene Eberbach and Peter Wegner. Beyond Turing machines. Bull. EATCS, 81:279-304, 2003.
• [10] Patrick C. Fischer. Generation of primes by a one-dimensional real-time iterative array. J. ACM, 12(3):388-394, 1965.
• [11] E. Goto. Ōtomaton ni kansuru pazuru [Puzzles on automata]. In T. Kitagawa, editor, Jōhōkagaku eno michi [The Road to information science], pages 67-92. Kyoristu Shuppan Publishing Co., Tokyo, 1966.
• [12] Joel David Hamkins. Infinite time Turing machines: Supertask computation. Minds and Machines, 12(4):521-539, 2002. arXiv:math.LO/0212047.
• [13] Joel David Hamkins and Andy Lewis. Infinite time turing machines. J. Symb. Log., 65(2):567-604, 2000. arXiv:math.LO/9808093.
• [14] M.L. Hogarth. Non-Turing computers and non-Turing computability. In BiennialMeeting of the Philosophy of Science Association, number 1, pages 126-138, 1994.
• [15] M.L. Hogarth. Predictability, computability and space-time. PhD thesis, University of Cambridge, UK, 2000. ftp://ftp.math-inst.hu/pub/algebraic-logic/Hogarththesis.ps.gz.
• [16] Wim Hordijk, Cosma Rohilla Shalizi, and James P. Crutchfield. An upper bound on the products of particle interactions in cellular automata. Phys. D, 154:240-258, 2001.
• [17] Andrew Ilachinski. Cellular automata -a discrete universe. World Scientific, 2001.
• [18] G. Jacopini and G. Sontacchi. Reversible parallel computation: an evolving space-model. Theoret. Comp. Sci., 73(1):1-46, 1990.
• [19] Mariusz H. Jakubowsky, Ken Steiglitz, and Richard Squier. Computing with solitons: a review and prospectus. in [1], pp. 277-297, 2002.
• [20] K. Lindgren and M. G. Nordahl. Universal computation in simple one-dimensional cellular automata. Complex Systems, 4:299-318, 1990.
• [21] Seth Lloyd and Y. Jack Ng. Black hole computers. Scientific American, 291(5):31-39, November 2004.
• [22] Jacques Mazoyer. Computations on one dimensional cellular automata. Annals of Mathematics and Artificial Intelligence, 16:285-309, 1996.
• [23] Jacques Mazoyer. On optimal solutions to the Firing squad synchronization problem. Theoret. Comp. Sci., 168(2):367-404, 1996.
• [24] M. Minsky. Finite and infinite machines. Prentice Hall, 1967.
• [25] Jacques Mazoyer and Véronique Terrier. Signals in one-dimensional cellular automata. Theoret. Comp. Sci., 217(1):53-80, 1999.
• [26] Pawel Siwak. Soliton-like dynamics of filtrons of cycle automata. Inverse Problems, 17:897-918, 2001.
• [27] V. I. Varshavsky, V. B.Marakhovsky, and V. A. Peschansky. Synchronization of interacting automata. Math. System Theory, 4(3):212-230, 1970.