Abstract geometrical computation for Black hole computation

Jérôme Durand-Lose

Description

Signal machines Computability Black hole effect Abstract geometrical computation for Black hole computation Jerome Durand-Lose Laboratoire d'Informatique Fondamentale d'Orleans, Universite d'Orleans, Orleans, FRANCE Computations on the continuum Lisboa, June 17th, 2005 Jerome Durand-Lose Abst. geom. comp. & black hole comp.

• straining iterated


• black hole


• introduction black hole


• laboratoire d'informatique fondamentale d'orleans


• black hole effect


• black hole model

Sujets

• Black Hole

Informations

• Publié par: pefav
• Nombre de lectures: 35
• Langue: English
• Poids de l'ouvrage: 2 Mo

Extrait

Signal machines
Computability
Black hole efiect
Abstract geometrical computation for
Black hole
J¶er^ ome Durand-Lose
Laboratoire d’Informatique Fondamentale d’Orl¶eans,
¶Universit¶e d’Orl¶eans, Orleans, FRANCE
Computations on the continuum
Lisboa, June 17th, 2005
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Computability
Black hole efiect
Introduction
Black hole computation
Cellular automata
Signal machines
Deflnition
Restriction
Computability
2-counter automata simulation
Black hole efiect
Straining
Iterated shrinking
Conclusion
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Introduction
Black hole computation
Cellular automata
Signal machines
Deflnition
Restriction
Computability
2-counter automata simulation
Black hole efiect
Straining
Iterated shrinking
Conclusion
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Black hole model
Observer
[Hogarth 94 & 00]
[Etesi & Nemeti 02]
1. Observer at the \edge"
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Black hole model
Observer
[Hogarth 94 & 00]
[Etesi & Nemeti 02]
1. Observer at the \edge"
2. Machine sent into the black hole inflnitely accelerated
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Black hole model
Observer
[Hogarth 94 & 00]
[Etesi & Nemeti 02]
1. Observer at the \edge"
2. Machine sent into the black hole inflnitely accelerated
3. Message sent by the machine received by the observer
within a bounded delay
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Malament-Hogarth space-time
Observer’s life-line
Possible messages
Maximum delay Black hole
Machine inflnite time ahead of it
Message indicates the result of the computation
After the delay, the observer knows whether the stops
Any recursively enumerable problem can be decided!
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Related models
Main idea: inflnitely many \iterations" on a sub-time-scale
Can be achieved with a transflnite ordinal scale as in:
Inflnite time Turing machines
[Hamkins 02]
Or with a \Zeno" sub-scale as in:
Piecewise constant derivative systems
[Asarin & Maler 95, Bournez 99]
We use the last approach
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Introduction
Black hole computation
Cellular automata
Signal machines
Deflnition
Restriction
Computability
2-counter automata simulation
Black hole efiect
Straining
Iterated shrinking
Conclusion
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.Signal machines
Black hole computation
Computability
Cellular automata
Black hole efiect
Starting from discrete model...
Cellular automata
ZQ
bi-inflnite line of states
jQj <1
Zcontinuous dynamical system over Q
9
local >=parallel Zupdating of Q
synchronous >;
uniform
J¶er^ ome Durand-Lose Abst. geom. comp. & black hole comp.