Jérôme Durand-Lose
email: lose@univ-orleans.fr

Abstract Geometrical Computation and Computable Analysis

Keywords: Analog computation, Abstract geometrical computation, Computable analysis, Signal machine, Type-2 Turing machine

Introduction

Classical computability deals with integers, finite sequences of letters, and more generally up to countably many discrete values. Does this mean that Analysis and Engineering are totally disconnected from computations? That physical simulation is impossible in silicon? Of course not, this is done everyday.

Dealing with real values is handled in various ways: fixed approximation (π is 3.14), formal manipulation (π is PI), unbounded approximation on demand (π is generated by a program that can provide extra digits at any time), interval arithmetics (π is included in [3.1, 3.2]). . . Following their definition as Cauchy sequences of rational numbers, real numbers can be encoded by infinite decreasing sequences of intervals with rational endpoints, such that their length tends to zero. The whole infinite sequence represents exactly one real at its intersection, but a finite prefix of the sequence is enough to get an approximation, the larger the prefix, the better the approximation. Rational endpoints allow exact coding and manipulation of each interval in classical computation, so that the infinite sequence of intervals can be written as an infinite sequence of symbols. Functions over these infinite sequences provide functions on the reals. A Turing machine is used: the infinite entry is written on one tape and the output is expected on a write-once tape (extra working tapes are available). To entirely process the input and generate the whole output, an infinite number of iterations is needed, but in finitely many an approximation is generated.

This approach, now called Computable Analysis (CA) was initiated by [START_REF] Turing | On computable numbers, with an application to the entscheidungsproblem[END_REF], then [START_REF] Grzegorczyk | On the definitions of computable real continuous functions[END_REF] and is detailed in classical books [START_REF] Ko | Computational Complexity of Real Functions[END_REF][START_REF] Weihrauch | Introduction to computable analysis[END_REF]. It was proven equivalent to a variation of Shannon's General Purpose Analog Computer [START_REF] Bournez | Polynomial differential equations compute all real computable functions on computable compact intervals[END_REF]. Another approach to analog computing is to imagine that values and primitives are freely available which leads to the Blum, Shub and Smale (BSS) model [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF].

In recent years, Abstract Geometrical Computation (AGC) has been developed and proven able to simulate the original BSS [START_REF] Durand-Lose | Abstract geometrical computation and the linear Blum[END_REF][START_REF] Durand-Lose | Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model[END_REF]]. In the present paper, AGC is shown capable of carrying out any CA-computation. An intermediate representation of real numbers with finitely many signals is provided. This encoding allows to go and return between BSS-encoding and CA-encoding.

Abstract Geometrical Computation is defined by dimensionless signals moving in an Euclidean (continuous) space in continuous time. To each signal corresponds a meta-signal which defines its speed. The number of meta-signals is finite. Existing signals are only modified when they collide: they are replaced by new signals according to their meta-signals and collision rules. A signal machine collects the definition of available meta-signals and collision rules.

In previous works to implement the BSS-model, real numbers are encoded by the distance between two parallel signals (plus two more signals to encode the scale, i.e. distance 1). On one side, for CA, this is not so convenient since infinite sequences are expected. On the other side, in the AGC context, infinitely many signals would either occupy the whole infinite space or produce singularities (accumulation of signals in a configuration, static) or accumulations (of collisions in the space-time diagram, dynamic) -preventing the values from being moved around.

These are very powerful yet dangerous artifacts. Special care has to be taken in defining the space-time diagram near them. A singularity lasts in the following configurations as long as signals are accumulating there. Anything colliding with it just gets absorbed. Unless a singularity is generated, an accumulation results in one signal (always the same). More complex rules can be devised to handle singularities and accumulations -but are not used here -so as to emulate the (nested) black hole model of computation [START_REF] Hogarth | Non-Turing computers and non-Turing computability[END_REF][START_REF] Etesi | Non-Turing computations via Malament-Hogarth space-times[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 1: Embedding black hole computations with rational numbers[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF] (with the use of folding structures) as well as to achieve exact multiplication of real numbers to simulate the BSS model [START_REF] Durand-Lose | Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model[END_REF].

To avoid handling infinitely many signals outside of CA-computations, an intermediate representation is used. A real number x is encoded by n + ε where n is an integer and -1 < ε < 1; n is encoded in signed binary and ε as a distance between two signals (a pair of signals somewhere in the configuration amounts for distance 1). The encoding used for CA implementation is signed binary with symbols 1, 0, 1 plus a decimal point. To go forth and back between the encodings, n is encoded as a sequence of signed bits (and thus does not have to be taken care of) and the first approximation is (n -1, n + 1). Then the approximation goes by steps: the interval (a, b) is replaced by (a, a+b 2 ), ( 3a+b 4 , a+3b 4 ) and ( a+b 2 , b) that corresponds to 1, 0 and 1 respectively. (Of course, intervals overlap and the infinite sequence is not unique.) All the geometric constructions to encode and to decode are presented.

The presentation of the implementation of Turing machines (TM) is only illustrated; it is quite straightforward and already done in [START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF]. Type-2 TM need infinitely many iterations to complete a computation. To get the results in finite duration, TM and input are embedded into a folding structure as in [START_REF] Durand-Lose | Abstract geometrical computation 1: Embedding black hole computations with rational numbers[END_REF][START_REF] Durand-Lose | Abstract geometrical computation 3: Black holes for classical and analog computing[END_REF]. The output is an infinite convoy of signals, bringing forth singularities. It is shown how this can be handled and used to produce the exact intermediate representation.

Definitions of AGC and CA are gathered in Section 2. Section 3 concentrates on approximation, i.e. the intermediate representation as well as how to get/add bits, and the simulation of Turing machines. Section 4 deals with exact computation in finite duration. Section 5 concludes this paper.

Definitions

Abstract Geometrical Computation

A signal machine (SM) is defined by (M, S, R) where M (meta-signals) is a finite set, S (speeds) a mapping from M to R, and R (collision rules) a function from the subsets of M of cardinality at least two into subsets of M (all these sets are composed of meta-signals of distinct speeds). A signal machine is extended if some meta-signal µ S is distinguished to be used as the result of an accumulation.

Each instance of a meta-signal is a signal located on the real axis. The mapping S assigns speeds to signals. A collision rule, ρ -→ρ + , defines what emerges (ρ + ⊆ M ) from the collision of two or more signals (ρ -⊆ M ). Since R is a function, SM are deterministic. The extended value set, V , is the union of M and R plus three symbols: ⊘ for void, S for accumulation, and c for singularity

. A configuration, c, is a mapping from R to M ∪ R ∪ {⊘} such that the set { x ∈ R | c(x) = ⊘ } is finite. An extended configuration, is a mapping from R to V such that all and only accumulation points of { x ∈ R | c(x) = ⊘, c } have the value c.
The locations of the c are thus defined in a static way: they only depend on the configuration and not on the dynamics.

A (resp. extended) space-time diagram is a mapping from an interval of R (representing the time) into (resp. extended) configurations. A signal corresponding to a meta-signal µ at a position x, i.e. c(x) = µ, is moving uniformly with constant speed S(µ). A signal must start (resp. end) in the initial (resp. final) configuration or in a collision. At a ρ -→ρ + collision, signals corresponding to the meta-signals in ρ -(resp. ρ + ) must end (resp. start) and no other signal should be present. There is a S if and only if there is no c and collisions are accumulating (from before, this one is dynamic). A S immediately turns into a (regular) µ S signal, so that a µ S signal can also result from an accumulation. Continuation rules could be designed to distinguish more cases, but this is useless here.

Space-time diagrams are represented with time increasing upward. The traces of signals are line segments whose directions are defined by (S(.), 1) (1 is the temporal coordinate) so that the speed is the inverse of the slope. Collisions correspond to the common extremities of these segments.

Computable Analysis

A type-2 Turing machine (T2-TM) is a regular Turing machine (TM) such that the entry is an infinite sequence of symbols written on a read-only tape. The output is also expected to be an infinite sequence of symbols written on a write once tape (each cell can only be written once). The TM has an extra work tape on which it can freely read and write. It needs infinitely many iterations to read a whole input and write a whole output, but after finitely many iterations, a finite part of the entry is read and a finite part of the output is generated. Since the output is write-once, anything written never changes and it converges to the infinite output according to the prefix topology.

To link this machinery to analysis, a representation of real numbers by infinite sequences should be provided. The larger the prefix of the representation is read, the more should be known on the encoded real number x, ultimately x should be perfectly known and distinguished from any other real number. The standard representation of a real number x is by any decreasing sequence of open intervals with rational ends such that their intersection reduces to {x}. The infinite sequence is then just the self-delimiting concatenation of the naming of the intervals. In the present paper, an equivalent representation is used.

Let Σ = {•, 1, 0, 1}, the signed binary representation, ρ sb :⊆ Σ ω -→ R, (from [Weihrauch, 2000, Def. 7.2.4 p. 206]) is defined only for infinite sequences with only one dot (•) by:

n 0 •d 1 d 2 d 3 . . . d n . . . -→ ν sb (n 0 ) + 1≤i d i 2 i
where n 0 ∈ {1, 0, 1} * , d i ∈ {1, 0, 1} and ν sb is a naming of natural integers signed in base 2 (1 representing -1). Only the open intervals

I n,k = ( n-1 2 k , n+1 2
k ) (n, k ∈ N) are considered; this family of intervals generates the usual topology on R.

This section deals with finite run of T2-TM. After defining the intermediate representation of real numbers and the extraction of signed bits, TM implementation is presented. The section ends with approximating the intermediate representation from a sequence of signed bits.

Intermediate representation and decoding

In the signed binary representation, there are finitely many symbols before the dot and then an infinite sequence of symbols in {1, 0, 1}. The first part, including the dot, is encoded by signals, one signal for each symbol. The second part represents a real number, ε, in (-1, 1) as a signed binary infinite sequence. This number is represented in AGC, by the distance between two signals (there exist two signals somewhere representing the scale, i.e. their distance is 1).

The integral part is represented by parallel vertical signals (1, 0 or 1) that get transformed into 1 L , 0 L or 1 L on receiving get (the signal sent to extract the next bit). The dot is treated similarly. These are not addressed in this paper.

The two signals to represent ε are zero and e. More signals are present: one, half, half and one at position respectively -1, -1 2 , 1 2 and 1 (position 0 is the one of zero). Signal e is between one and one, it might be superposed with half or zero, in such a case a different meta-signal is used (these technical details are omitted from now on).

Signed bits are extracted one after the other and companion signals are prepared for next extraction: one, half, zero, half and one are scaled by one half and e is translated in order to correspond to the remainder. The structure on Fig. 1(a) is used for this. The three main cases are represented on Fig. 1 where signal zero (in the middle) and the one handling e are drawn with thick lines. If -1 < ε < -1 2 n then the extracted bit is 1 (signal 1 L exits on the left) and ε is replaced by ε+ 1 2 n (e is shifted by the distance from one to half).

If -1 2 n < ε < 1 2 n
then the extracted bit is 0 (signal 0 L ) and ε is kept (e is not shifted). Except for the geometric construction, the last case is symmetric to the first one. Arbitrarily, if -1 2 < x < 0, then the extracted bit is 0 although it could have been 1, similarly for 0 < x < 1 2 . There is no room in the paper to detail all the meta-signals and rules. The corrections of the various constructions rely on simple geometry. All have been checked and implemented in Java to generate the pictures.

Computable Analysis

A type-2 Turing machine is nothing but a regular TM that is supposed never to halt with two special purpose tapes: one initially totally filled -inputand one for writing once -output. On the input tape, the head cannot change the read symbol nor move left (i.e. back to the start). On the output tape, the head either rewrites the blank symbol or moves right. In the transition table, transitions that read on the input can be clearly identified. Reading is replaced by sending a get signal to the intermediate structure and waiting for the signed bit. The same is done with writing, in this case, signals encoding signed bits are sent on the side but no acknowledge/returned value is expected (next subsection presents how to deal with them). Implementing a TM in AGC has already been done in Durand-Lose [2009]. One work tape is enough; read and write operations are carried out by signals sent on the side (an answer is expected for reading). The simulation cannot be used straightaway because on an infinite run, the tape might extend infinitely, so that with previous construction, the room used for the tape becomes infinite. Since space is continuous, it is pretty easy to put less and less space between signals amounting for the cells of the tape. Indeed, a geometric decreasing is used so that each signal is half the distance from the last than the distance to the last from the previous one. This is illustrated on Fig. 2 with the first iterations of a TM, the initial implementation and the one within bounded space.

1 L e (b) -1 < ε < -1 2 0 L e (c) -1 2 < ε < 1 2 1 L e (d) 1 2 < ε < 1
These signals might go accumulating if the head is moving right forever. But in a proper CA-computation, it is not the case: there must be infinitely many readings and each one needs signals to go forth and back from the tape to the intermediate structure. Since this distance is bounded away from zero, each reading requires a minimal time. There is no accumulation whatsoever in a normal computation. A bounded space is used by the T2-TM simulation and the encoded real number. There is always finitely many signals in any configuration.

In case of multiple input (for example for an addition), it is easy to set one after the other on the right and to have a distinct get for each entry.

Approximating the intermediate representation

Since only approximation is concerned in this Section, only a tightening bound on ε is generated. The first bits for the integral part are encoded as they are in a geometric positioning to ensure that they remain in a bounded space. Only the fractional part needs careful attention. At start, there are five signals to encode , 2009, Fig. 6] (c) finite space version (with more transitions) Fig. 2. Simulation of a Turing machine.

a b q 0 . . . b b q 0 . . . b c # q 0 . . . b c b q 1 . . . b b b q 1 . . . b b c # q 1 . . . b b c a # q 1 . . . b b c a a # q 1 . . . (a) TM computation q 0 a q 0 b q 0 # c q 1 b c q 1 q 1 b q 1 # c a q 1 q 1 # b b c a a q 1 (b) [Durand-Lose
-1, -1 2 , 0, 1 2 , and 1 at their correct relative positions (obtained for example by copying) and the approximation is up to 1. The problem is then to locate the position of e: it is somewhere between signals one and one. Each incoming bit allows to scale down the interval. Figure 3 shows the three cases. For exact values, next section considers infinite incoming sequences of signed bits in bounded space. Considering an incoming finite sequence of signed bits or convoy, the tightening for one bit should not mess with the one of another bit so delays have to be provided. Delaying is done by replacing the incoming signals by null speed signals (recording the bits). This replacement is carried out by some toggle signal. When the delay has elapsed, another toggle signal is sent to restore their movement. The first toggle is launched when the first remaining signal (the new one) is generated, the second toggle at the second one (the new half) as illustrated on Fig. 4 where an extra signal is added on the right to stop the toggles.

(a) for 0 0 0 0 0 0

(b) for 1 1 1 1 1 1 (c) for 1 1 1 1 1 0 c (d) for 1 1 1 1 1 0 1 1 1 1 1 0 . . .

Exact computation

Folding and extended signal machines

Except for the output signals, the Type-2 Turing machine and the input use a bounded portion of space during the whole computation. There exist constructions to fold into a bounded space and bounded time a spatially bounded infinite time computation. They can be used to fold the computation without interfering with the output signals: by running through the collision rules and cancelling any action that the folding structure would have on them, they become insensible to the folding. Inside the structure, the computation is scaled down, generating an infinite acceleration (used to emulate the black hole in Durand-Lose [2006,2009]). This way in finite time, the whole infinite output is generated and exits the structure as displayed on Fig. 5.

Inside the folding structure, the Turing machine has an infinite time ahead of it. The structure preserves ratios in the understanding that there are infinitely many pieces at different scales that reform the original space-time diagram after rescaling and translating. This means that even though the intermediate representation suffers multiple rescaling, it still generates the same infinite sequence, and the TM the same output.

The output is an infinite convoy in bounded space. This uses the extended context. There is a companion singularity c (on the top of it). configuration, infinitely many signals accumulate there; so c prevents S even though collisions are accumulating. The intermediate structure also produces an accumulation of collisions; but this time, there is no signal around it. So that one S is generated and immediately turns to µ S . This µ S is located exactly where e should be and the speed of µ S is chosen null. This is illustrated on figures 4(d) and 5.

CA-representation to intermediate representation

A signal set is sent to turn µ S into e so that the two signals are distinct. Sending this signal is not complicated. Indeed the space-time location of the last accumulation is bounded easily: the c path starts from the top of the folding structure (this location is known from construction), then the movement of the infinite convoy is the sum of a left translation and the sum of a geometric series.

Conclusion

Theorem 1. With a proper handling of accumulations of collisions and of signals, it is possible to compute any function of computable analysis. Moreover, even if the computation involves infinitely many signals present simultaneously in a bounded space, there are finitely many signals in the initial and final configurations.

There is no hidden oracle. Although speeds may be any real and thus encode information, only a few integral values are used. And apart from intermediate representation of ε, the distance between signals are also proportional with rational ratio. Nevertheless such "extra information" could be provided to compute at different level of CA-hierarchies.

Not only does the intermediate representation use finitely many signals, but is also almost directly reusable to do analog computation in the Blum-Shub-Smale understanding (as presented in [Durand-Lose, 2007[START_REF] Durand-Lose | Abstract geometrical computation with accumulations: Beyond the Blum, Shub and Smale model[END_REF]). This leads to consider even more powerful analog computational system since CA and BSS are not comparable, e.g. analytic machines [START_REF] Chadzelek | Analytic machines[END_REF].

It should also be possible to use higher order accumulation to hyper-compute as is done for the BSS model in Durand-Lose [2009] and to do some real hypercomputing [START_REF] Ziegler | Short) Survey of real hypercomputation[END_REF] (although, just by being able to do linear BSS computation without the extended context, or with the intermediate representation, it can already compute the sign in finite time!).

Fig. 1 .

 1 Fig. 1. Extracting a single signed bit.

Fig. 3 .

 3 Fig. 3. Tightening the intermediate representation.

Fig. 4 .

 4 Fig. 4. Management of three finite convoys and an infinite one.

Fig. 5 .

 5 Fig. 5. Global structure.


Jérôme Durand-Lose

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

come

Introduction

No position is taken on the theoretical and practical feasibility of using any potentially existing particular black hole for hyper-computing. The reader is referred to other contributions in this issue as well as [START_REF] Etesi | Non-Turing computations via Malament-Hogarth space-times[END_REF]; [START_REF] Németi | Relativistic computers and the Turing barrier[END_REF]; [START_REF] Németi | Can general relativistic computers break the Turing barrier[END_REF] for clear introductions and surveys on this topic. All the work presented here in done the context of so-called "Malament-Hogarth" space-times [START_REF] Mark | Non-Turing computers and non-Turing computability[END_REF][START_REF] Mark | Deciding arithmetic using SAD computers[END_REF] and not slowly rotating Kerr black hole. The main differences are that, one, the observer remains out of the black hole and second, nested black holes are considered.

Black hole computation works in the following way. At some location 1 an observer starts a computing device which he sends on a different worldline such that: at some point, after a finite time on his own world-line the observer has the whole future of the device infinite world-line in its causal past and the device can send some limited information to the observer. The device has an infinite time for computing ahead of it and can send a single piece of information to the observer. Not only can the observer perceive this piece of information, but after a finite duration which he is aware of, the observer knows for certain that if he has not received anything then the machine never sends anything during its whole, possibly infinite, computation. So that, for example, if the piece of information is sent only when the computation stops, at some point, the observer knows for certain whether the computation of the machine ever stops.

From the computer scientist point of view, this allows to have some piece of information on a whole, potentially infinite, computation. This way the Halting problem or the consistency of many first order logic theory (e.g. Set theory or Arithmetic theory) can be decided. This clearly falls out of the classical recursion/computability theory since it allows to decide semidecidable subsets (Σ 0 1 in the arithmetic hierarchy). Malament-Hogarth space-times allow to have nested black holes, and are called arithmetical sentence deciding (SAD) [START_REF] Mark | Non-Turing computers and non-Turing computability[END_REF][START_REF] Mark | Deciding arithmetic using SAD computers[END_REF]. With each infinite level of nested black-holes, the computing power climbs up a level of the arithmetic hierarchy (and even the hyper-arithmetic hierarchy in second order number theory [START_REF] Welch | The extentent of computation in malamenthogarth spacetime[END_REF]). The arithmetic hierarchy is formed by recursive predicates preceded by alternating quantifiers on natural numbers. The level in the hierarchy is defined by the first quantifier and the number of alternations.

In computer science, considering and continuing a computation after its potential infinite span exist in various form. Infinite time Turing machines [START_REF] David | Infinite time Turing machines[END_REF][START_REF] David | Infinite time Turing machines: supertask computation[END_REF][START_REF] David | A survey of infinite time Turing machines[END_REF]Copeland, 2002) consider ordinal times (and values); the main difference is that the limit of the tape is available, whilst with black holes only a finite and bounded piece of information is available. Infinite computations also provide limits, for example computable analysis (Weihrauch, 2000, type-2 Turing machines) manipulates infinite inputs and generates infinite outputs, each one representing a real number. In analog computations, limit operators (as limits of sequences of real numbers) are also considered [START_REF] Chadzelek | Analytic machines[END_REF][START_REF] Kawamura | Type-2 computability and Moore's recursive functions[END_REF]Mycka, 2003b[START_REF] Mycka | Analog computation beyond the Turing limit[END_REF][START_REF] Mycka | A new conceptual framework for analog computation[END_REF][START_REF] Bournez | On the computational capabilities of several models[END_REF].

The setting in which the black hole effect is simulated here is not the solution to any relativity equations. It is rather something that is constructed inside a Newtonian space-time and provide the desired effect whereas black holes involves non-Euclidean geometry (like the Schwarzschild one). Any initially spatially bounded computation can be embedded in a shrinking structure resulting in the same computation happening in a spatially and temporally bounded room, even if it was not the case before. This structure provide the black hole, outside of it, some information may be received to gain some insight on what happen inside.

Abstract geometrical computation (AGC) deals with dimensionless signals with rectilinear and uniform movement in a (finite dimension) Euclidean space. It is both a continuous and an analog model. The way it is analog is quite unusual because there are finitely many values but continuum many variables. Time is evolving equally everywhere. What brings forth the accelerating power is that space and time are continuous so that Zeno effect can happen and indeed, everything heavily relies on it. Throughout the article, only dimension 1 spaces are considered, thus space-time diagrams are 2 dimensional.

Signals are defined as instances of meta-signals which are of finite number. They move with constant speeds uniquely defined by their meta-signals.

When two or more signals meet, a collision happen and they are replaced other signals according to collision rules. A signal machine defines the available meta-signals, their speeds and the collisions rules.

A configuration at a given time is a mapping from R to a finite set (containing the meta-signals) defining signals and their positions. Signals are supposed to be away one from another. The void positions (i.e. position with nothing) are supposed to form an open set. The rest of the configuration contains only singularities. They are many ways to continue a space-time diagram after an isolated singularity, the ones used here are: let it disappear or turn it into signals.

This model originates in discrete signals in Cellular Automata (Durand-Lose, 2008b). This explains the choice of finitely many meta-signals and constant speeds. There are other models of computation dealing with Euclidean spaces. [START_REF] Huckenbeck | Euclidian geometry in terms of automata theory[END_REF][START_REF] Huckenbeck | A result about the power of geometric oracle machines[END_REF] developed a model based on finite automata able to draw lines and circles and to compute intersections. Not only are the primitives different, but also it is sequential and depends on an external operator to perform the construction whereas in signals in AGC operate on their own. [START_REF] Naughton | On the computational power of a continuous-space optical model of computation[END_REF] presents an optical model manip-ulating continuous images (configurations are elements of {0, 1} R 2 + , but the primitives are also external and their actions non local. [START_REF] Jacopini | Reversible parallel computation: an evolving space-model[END_REF] developed an approach where a computation results in a polyhedron. They only encompass finite polyhedron (i.e. bounded with finitely many vertices) and allow surfaces and volumes of any dimensions while AGC has only lines.

Another model worth mentioning is the Piecewise Constant Derivative (PCD) system (Bournez, 1999b). There is only one signal, but its speed changes each time it enters a different polygonal region. Not only is AGC parallel but has no such things as boundaries. Nevertheless, PCD are able to hyper-compute and climb up the hyper-arithmetic hierarchy (Bournez, 1999a) while the other two cannot.

In AGC, since signals dwell in a continuous space (R) and time (R + ) and there is no absolute scale, it is possible to rescale a configuration. Rescaling a configuration rescales the rest of the space-time. An automatic procedure to freeze the computation, scale it down and unfreeze it, is provided. When this construction is made to restart it-self forever, a singularity is reached. Any AGC-computation starting with only finitely many signals can be embedded in this structure so that the corresponding computation is cut in countably many bounded pieces geometrically shrunk and inserted. This brings a general scheme to transform any AGC-computation into one that can do the same computation but in a piece of the space-time diagram bounded in both space and time. This is the desired black hole effect. Another shrinking scheme is presented in Durand-Lose (2006a), but it works only for spatially bounded AGC-computations while the one presented here does not impose this condition. The construction is detailed since AGC is not so well-known and it is the cornerstone of the results in the article.

Simulating a Turing machine (TM) is easy using one signal to encode each cell of the tape and an extra signal for the location of head and the state of the finite automaton. Any Turing machine simulation can be embedded in the shrinking structure making it possible to decide semi-recursive problems in finite time.

As long as speeds and initial positions are rational and there is no singularity, the location of each collision is rational (as the intersection of lines with rational coefficients). This can be computed in classical discrete computability (and have been implemented to generate figures). The model is also perfectly defined with irrational speeds and positions and can thus be also considered as an analog model. It has recently been connected to the Blum, Shub and Smale model of computation (which can perform algebraic operations, as well as test the sign, on real numbers with exact precision) [START_REF] Durand-Lose | Abstract geometrical computation and the linear Blum[END_REF], 2008a). In the present paper, it is only recalled how real numbers are encoded and how a singularity is used to provide the multiplication. Our shrinking scheme can be used in this analog context to answer analog decision problems.

The way a signal machine is transformed to have shrinking capability can be iterated so that singularities/accumulations of any order can be generated. This allows to decide a formula formed by a total (resp. BSS) recursive predicate preceded by a finite alternation of quantifiers on N (i.e. to climb the corresponding arithmetical hierarchies). For the analog case, this remains a quantification over a countable set2 .

In Section 2, the model and the shrinking structure are presented. In Section 3, the way discrete computation can be done and shrunk is presented. In Section 4, analog computation is considered. Section 5 explains how to have nested black holes so as to climb the arithmetic hierarchies. Section 6 gathers some concluding remarks.

Model and Mechanics

The underlying time is R + ; there is no such thing as a next configuration. The underlying space is R. A configuration is a mapping from R to a finite set (yet to be defined). A space-time diagram is a function from R × R + to the same finite set.

What lies on R are signals, collisions between signals or singularities (created by accumulations). Signals are moving with constant speed depending only on their nature. When they meet, an instantaneous collision happens and the signals are replaced by others according to some collision rules. A singularity happens when and where infinitely many collisions, signals and/or singularities accumulate. Ways to continue a space-time diagram beyond an isolated singularity are proposed at the end of this section.

Signal machines and space-time diagrams

Definition 1 A signal machine (SM) is defined by (M, S, R) where M (meta-signals) is a finite set, S (speeds) a function from M to R, and R (collision rules) a partial function from the subsets of M of cardinality at least two into subsets of M (all these sets are composed of signals of distinct speeds).

Each signal is an instance of a meta-signal. Its speed is constant and only depends on its meta-signal (given by S). When two or more signals meet, R indicates the signals to replace them. Meeting signals must have distinct speeds otherwise they are parallel and never meet. Signals are not allowed to be superposed, so that all signals emitted by a collision must also have distinct speeds.

Definition 2 The extended value set, V , is the union of M and R plus two special values: one for void, ⊘, and one for singularity i. An (valid) configuration is a total function from R to V such that all the accumulation points of its support (the set of non void location, supp(c

) = { x ∈ R | c(x) = ⊘ }) have the value i. A configuration is finite if its support is finite. It is simple if it is finite and i is not reached. It is rational if it is
simple and its support is included in Q. A SM is rational if all the speeds are rational numbers and only rational configurations are used.

As long as there is no singularity, a finite configuration is only followed by finite ones.

To be rational is robust. Signals at rational positions with rational speeds can only meet at rational location. All collisions happen at rational dates and at these dates the positions of signals are all rational. Since rational numbers can be encoded and manipulated exactly with any computer, rational SM can be handled inside classical computability theory.

Two results limit the interest and extend of rational SM. First, predicting whether a singularity ever happens is Σ 0 2 -complete (in the arithmetical hierarchy, which means not even semi-decidable) (Durand-Lose, 2006b) and second, a singularity can happen at an irrational position (Durand-Lose, 2008a). On the other hand, as long as Turing-computability is involved, rational SM are enough (as shown in Sect. 3). But if analog computations are to be considered, then it is not the case anymore as in Sect. 4.

Let S min and S max be the minimal and maximal speeds. The causal past, or backward light-cone, arriving at position x and time t, I -(x, t), is defined by all the positions that might influence the information at (x, t) through signals, formally:

I -(x, t) = { (x ′ , t ′ ) | x -S max (t-t ′ ) ≤ x ′ ≤ x -S min (t-t ′ ) } .
[0, T ] to V ) such that, ∀(x, t) ∈ R × [0, T ] : 1. ∀t∈[0, T ], c t (.) is valid, and c 0 (.) = c 0 ; 2. if c t (x)=µ ∈ M then ∃t i , t f ∈[0, T ] with t i <t<t f or 0=t i =t<t f or t i <t=t f =T s.t.: (a) ∀t ′ ∈ (t i , t f ), c t ′ (x + S(µ)(t ′ -t)) = µ , (b) ( t i =0 and c 0 (x i ) = µ ) or ( c ti (x i ) = ρ -→ρ + ∈R and µ ∈ ρ + ) where x i =x + S(µ)(t i -t) , (c) ( t f =T and c t f (T ) = µ ) or ( c t f (x f ) = ρ -→ρ + ∈R and µ ∈ ρ -) or c t f (x f )=i where x f =x + S(µ)(t f -t) ; 3. if c t (x)=ρ -→ρ + ∈ R then ∃ε, 0<ε, ∀t ′ ∈[t-ε, t+ε]∩[0, T ], ∀x ′ ∈[x-ε, x+ ε], (a) (x ′ , t ′ ) = (x, t) ⇒ c t ′ (x ′ ) ∈ ρ -∪ρ + ∪ {⊘}, (b) ∀µ∈M , c t ′ (x ′ )=µ ⇔ ∨ µ ∈ ρ -and t ′ < t and x ′ = x + S(µ)(t ′ -t) µ ∈ ρ + and t < t ′ and x ′ = x + S(µ)(t ′ -t) ; and 4. if c t (x) = i then ∀ε>0, there are infinitely many collisions in I -(x, t) ∩ R × [t-ε, t) or infinitely many signals in [x -ε, x + ε] × [t-ε, t) .
The definition naturally extends to the case T = +∞. A space-time diagram is rational if it is correspond to the one of a rational SM. As long as no singularity is reached, the evolution is deterministic; the space-time diagram only depends on c 0 and the SM.

2.1.1 Encompassing singularities. When a singularity is reached isolated (i.e. there is nothing round it), there are various ways to continue the spacetime diagram beyond it.

Definition 4 (Schemes to handle isolated singularities) A singularity at (x, t) is isolated if there is nothing but void around it in the configuration (i.e. ∃ε, ∀x In the two last schemes, µ s or the singularity rules have to be added to the definition of the SM. In such a case, one talks about an extended SM (ESM). Next sections consider ESM and the schemes used are indicated.

′ ∈ [x -ε, x + ε], x ′ = x ⇒ c t (x ′ ) = ⊘).
The first scheme is not considered here; although it makes sense since singularities generally do not just disappear, in dimension one, it unfortunately produces an unbreakable frontier definitively splitting the configuration in two. The second one is considered in the section on discrete computation while the third is considered in the section on analog computation. The reason in the analog case is that its position is an important piece of information. The last case is also used to consider the case of a singularity happening exactly on a higher level structure (as the one presented below) with nested structures in Sect. 5.

The last two schemes impose a modification of the rules of space-time diagrams. One is to allow a signal to start from a singularity to add to 2b "or ( c ti (x i )=i ∧ µ = µ s )" and to 4 something amounting for signals emitted like the rules for collisions (3) which is not given since it depends on the scheme and for the last scheme of the singularity rules.

In case of non-isolated singularities, the fist two schemes remain possible while the two last ones would make it necessary to define signals with a dimension (which might be not an integer since the accumulation set can be a Cantor set).

Accumulations of second (or more) order can be considered, as long as all the singularities are isolated. In the last case, more distinction could be made according to the level of singularity. As long as finitely many levels are considered or distinguished, the description remains finite.

Shrinking and space and time bounding

All the constructions work in the following way: starting from a SM, new meta-signals and rules are added in order to generate another SM that works identically with original meta-signals but the new ones provide an extra layer with some kind of meta instructions. For a computation to be altered, extra signals have to be added to the initial configuration.

Freezing and unfreezing.

A new meta-signal, toggle, with a speed strictly greater than any present speed, say s 0 is added. If one instance of toggle is set on the left, and is re-generated by every collision, then a succession of toggle (signals) crosses the entire computation. It is the freezing signal. Freezing is done in the following way: each time it meet some signal µ, it replaces it by some frozen counterpart F µ. All these new frozen metasignals have the same speed, say f 0 (which should be less that s 0 to ensure that they are above the freezing line on the space-time diagram). It might happen that the freezing signal passes exactly on a collision, say ρ. Then the collision is frozen too, i.e. it is replaced by a frozen signal amounting for it, F ρ. The signals resulting from the collision are generated when the collision is unfrozen.

The unfreezing scheme is the same, in reverse: signals and collisions replace their frozen counterparts at the passing of another toggle signal.

This scheme is illustrated on Fig. 1. In all the figures, time is elapsing upwards. On the left, one computation is showed unaltered but the intended trace of toggle is indicated with dotted lines. On the right, the computation is frozen, the frozen signals (the F .) are left to move for some time and then they are unfrozen by a second toggle. Signal are shifted on one side, they could be shifted on the other side by symmetry, or shifted anywhere (as long as it is in the future) by moving the toggling signals and changing the inner slope. The algorithm to modify a SM is given on Fig. 2 where object oriented notations are used. Each time new identities are created, renaming is used if necessary. There is nothing particular about it and every modification works on the same pattern.

Scaling parallel signals and any computation.

When signals are parallel, they remain so and do not interact, their structure is quite loose. So that a group of parallel signals can be manipulated quite easily as long as they remain parallel they remain synchronized. They just have to be unfrozen with the same slope.

Using a Thales based construction, or prismatic if thought of as light beams, it is easy to scale parallel signals as depicted on Fig. 3(a). The idea is to change the direction twice to be scaled and recover the original direction. The speed of the signals crossing the triangle is carefully selected in order to insure the wanted ratio. This construction can be set inside the freezing/unfreezing construction. This leads to the scheme of Fig. 3(b). The specially added signal for the structure are only a part of the ones in the next subsection. The algorithms to modify SM are so plain that they are not presented anymore.

Iterating forever.

The idea is to iterate ad infinitum above construction. More signals have to be added in order to restart the freeze, scale down and unfreeze process on and on. The structure and some basic properties are presented before the embedding of computations.

The structure is presented on Fig. 4. The collision rules are not given because they can be read directly from the figure; for example {toggleUnfr, axis} → {boundRi, axis, toggle} . The dashed axis signals are part of the construction, while the dotted lines do not correspond to any signal and are only there to delimit some regions. Signal axis is dashed because it does not delimit any region. The toggleUnfr and toggleFree signals are used to start the freezing and unfreezing toggle. The scale signals are used both to change the direction of parallel signals (and achieve scaling down the embedded configuration) and also to start boundRi. The signals boundLe and boundRi are used to bound the potential room used by the embedded computation when active. The initial position of axis is at one third of the distance between the four on the left and boundRi.

The construction works because the speed parameter ν 0 used to compute the various speeds is equal to the maximum absolute value of the speeds in the original SM. The speeds given on Fig. 4 are computed such that:

at each iteration, the structure is scaled by half; and the length of the unfreezing toggle signal is one fourth of the preceding freezing one.

The structure is twice as small and twice as fast each time but the initial computation is scaled by one fourth. Relatively to the structure the computation is two times faster each time. This is wanted because not only should the structure collapse in finite time, but meanwhile the embedded computation should have infinite time ahead of it. This is to be understood considering the regions.

The A i regions (on Fig. 4) are the ones where the embedded computation is active. The first one is triangular while all the other ones are trapezoidal. The other two regions are triangular. The F i regions are the ones where the embedded computation is frozen and signals follow the direction of the dotted line. The F ′ i regions are the ones where the embedded computation is also frozen but signals follow the direction of toggleUnfr. The frontiers between A i and F i (as well as F ′ i and A i+1 ) are toggle signals thus the correct freeze (and unfreeze). The frontiers between F i and F ′ i are scale signals which correspond to a change of direction of frozen signals.

On the frozen regions F i , all frozen signals have to be parallel to the dotted line in order that the lower toggle is "mapped bijectively" onto scale. So that their speed is -8 5 ν 0 . On F ′ i all frozen signals have to be parallel to the scaleLo signal in order that scale is "mapped bijectively" onto the upper toggle. So that their speed is 1 2 ν 0 (toggleUnfr). The embedded configuration is scaled by one fourth but the piece is only one half in size of the previous one. Each time the duration, relatively to the original computation, is halved by 2 (for the structure size) but multiplied by 4 for the scale. Altogether, the ratio is 2. So that each time, the elapsing time for the original computation is doubled. This ensures that the original computation is entirely embedded, i.e. has infinite time ahead of it.

Figure 5 shows a simple space-time diagram that is growing on both side on the left and its embedded version on the right. The active part is where the lattice is visible, otherwise it is frozen, shift and scaled.

The location of the singularity can be computed easily as the intersection of two lines (but also as a geometrical sum) and is rational as long as it is stated with rational positions. The shrinking structure serves as a black hole. The configuration embedded inside is trapped. In the following sections, small modifications of already modified SM show how to let some information leave.

Discrete computations

Definition 5 A Turing machine (TM) is defined by (Q, q i , Γ, ^, #, δ) where Q is a finite set of states, q i is the initial state, Γ is a finite set of symbols, ^, tape head, and #, blank, are two distinguished symbols, and δ :

Q × Γ → Q × Γ × {←, →} is the transition function.
A TM-configuration is defined by (q, w, i) such that q is a state, w is a finite sequence of symbols -or word over Γ -and i is a natural number. The automaton is in state q, w (completed by #'s) is written on the tape and the head is over the ith cell of the tape. The TM is self-delimiting when there is only one ^on the tape which is written on the first cell, and there is nothing but # right of the first #. If it is not the case, the TM is in an illegal configuration.

The next configuration is defined by the transition function as follows. If δ(q, w i ) = (r, a, →) then the next configuration is defined by (r, w ′ , i + 1) where w ′ is obtained from w by replacing the ith symbol by a. If δ(q, w i ) = (r, a, ←) then, if i = 0 then the TM stops otherwise the next configuration is defined by (r, w ′ , i -1).

The TM computes in the following way: some input (without ^and #) is written on the tape preceded by ^and followed by potentially infinitely many #. The result of the computation, if any, is what is written on the tape (^and all # are discarded) when the TM stops.

The TM halts normally when the head tries to leave the tape. For example, the machine defined on Fig. 6(b), computes on Fig. 6(a) with the entry ab. The output is bbab. If the computation does not halt or enters an illegal configuration, the output is undefined.

When a TM is used for a decision (yes/no output), the states are partitioned into accepting and refusing one. The answer is then given by the state in which it halts.

Turing-machine simulation

The simulation goes as follows: there are finitely many parallel signals encoding the content of the tape in-between which zigzags a signal mimicking the movement of the head and encoding the state. This is depicted with an example on Fig. 6(d).

δ ^a b # qi qi,^,→ qi,a,→ q1,a,← - q1 - q1,b,→ - q2,a,→ q2 - - - q f ,b,← q f q f ,^,← q f ,a,← q f ,b,← - (b) Transition table of the TM. General case δ(q, c) = (r,d,→) d c - → r - → q d c - → r ← -q δ(q, c) = (r,d,←) d c ← -r - → q d c ← -r ← -q Special rules δ(q, #) = (r, d, →)δ(q, #) = (r, d, ←) d # - → r - → q ← - # d # ← -r - → q ← - # - → # d - → # - → q - → r ← - # d - → # - → q ← -r ← - # - → # e ∈ Γ e e - → # ← - # # - → # - → # (c) Generation of Rules.
- → qi - → qi - → qi ← - q1 - → q1 - → q1 - → q2 ← - # - → # ← - q f ← - # - → # ← - q f ← - # - → # - → # # ← - q f ← - q f ← - q f (d) Simulating space-time diagram.
Fig. 6 Example of a TM computation and its simulation by a SM.

The simulating SM is defined by the following meta-signals:

one symbol signal for each value in Γ , with null speed, to encode the cells of the tape; --→ q (of speed 1) and ←q (of speed -1) head signals for each state q, to encode the state and the location and movement of the head;

-# (of null speed), ← -# (of speed -3), -→ # (of speed 3), and -→ # (of speed 1) which are used to denote the end of the tape and manage the enlargement of the tape.

The initial SM-configuration for a TM-computation on the entry w = w 1 w 2 . . . w k is generated by putting one -→ q i -signal at position -1, one ^signal at position 0, one w i -signal at position i (1 ≤ i ≤ k), and one #-signal at position k + 1, A SM-configuration encodes a TM configuration if it corresponds to the same sequence of symbols (up to extra #'s at the end) closed by a # with an extra signal encoding the state and moving to meet the signal corresponding to the position of the head.

The collision rules ensure that the evolution of the SM corresponds to the computation of the TM. When the head encounters a symbol signal, it performs the update and move to its next position on the tape. When it meets the right special signal, the configuration is automatically enlarge.

The generated collision rules are given on Fig. 6(c). When a rule is not defined, the signal just cross unaffected. From top to bottom, they correspond to the following cases. For each TM-transition, two collision rules are generated, they correspond to the cases where the head would come from the left or from the right. The special rules are made in order to ensure a correct enlargement of the configuration in the case a head signal meet #, the signal marking the last cell. In such a case, two things have to be done: normally do the TM-transition (as if it were a # signal) and enlarge the configuration. The latter means generate one # one position on the right if the head goes left (left side rules). If the head goes right (right side rules), then it should be taken care that the head meets something on the right (lower row rules). This is illustrated in the middle of Fig. 6(d). In each first case, a ← -# is sent on the left. It bounces on the symbol signal on the left (bottom rule of Fig. 6(c)) and is replaced by -→ # , cross whatever signal present to get where would be the head if it would have gone right. If indeed the head went right, it is met and the TM-transition is done and the configuration enlargement starts again. If it is not the case (left rules of Fig. 6(c)), then -→ # is sent in order to meet -→ # and place the new #. Signals ← -# and -→ # are three time faster in order to ensure that the meeting happens exactly where the next symbol signal should have been.

At the end of the TM-computation simulation, the signal encoding the state goes out on the left. The process is robust, the positions does not have to be exact as long as the order of the signals is preserved. It can be implemented with a rational SM.

Infinite Turing computation in bounded time

The construction described in Sect. 2 rightfully apply to the above construction. It is considered that the singularity vanishes leaving no signal (scheme 2 of Def. 4). The infinite acceleration is granted. But the information leaving the black hole is missing. The ESM has to undergo some modifications. The first one is to generate the escaping signal, the second to retrieve it.

The result of a deciding TM is given by the new state whenever it performs a transition on ^and sends the head on the left. These transitions are clearly identified in the transition table of the TM. So there are also clearly identified in the rules of the simulating ESM.

Once the shrinking mechanics have been added, the rules can be changed so that to generate new signals amounting for accept and refuse. These signals are unaffected by other signals including the structure ones. Their speed is -1 so that they exit on the left.

The last thing is to add two signals horizonLe and horizonRi of speed ( 1 5 ν 0 and -16 15 ν 0 ) on the left and right of the shrinking structure. Their speeds ensure that they remain at constant distance from the structure. The way these signals are intended to work is displayed on Fig. The desired effect is achieved. Recursively enumerable problems (Σ 0 1 ) can be decided and computation can carry on after the answer is known.

Analog computations

In this section, analog computations in the understanding of the Blum, Shub and Smale model [START_REF] Blum | On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines[END_REF][START_REF] Blum | Complexity and real computation[END_REF] (BSS for short) are considered. After briefly presenting the BSS model on R and its linear restriction, results on its simulation in AGC are recalled before the shrinking construction is applied.

BSS Model

BSS machines (BM) operate like TM on unbounded arrays/tapes. Each cell of the array hold a real number and all the computations are made with exact precision. The BM has a head allowing to access a finite portion of the tape called a window. It has finitely many states and to each one corresponds an instruction among the following:

1. compute a polynomial function of the window and place the result in it; 2. test for the sign of a given cell in the window and branch accordingly; 3. shift the window one cell on the left or on the right; and 4. halt.

The window is shifted by one cell so that consecutive windows overlaps. This is used to carry information around, since the BM has no real value storage on its own.

A BSS machine is linear if instruction 1 is replaced by "compute a linear function [. . . ]". Thus multiplication is allowed only if it is by a constant.

Like for TM, the input (resp. output) is the content of the array when the BM is started (resp. halts). Comparing to TM, trying to leave the array on the left is an error but halting states are provided. If BM are used for decision, then there are distinct halting states for acceptance and refusal.

The simulation is not presented since details are not relevant to the following. Only the encoding of real values and two main results are given.

A real number is encoded as the distance between two signals. But as it has already been guessed by the reader, time and distance are very relative concepts. The distance between two scale signals is thus used as a scale. The same scale is used for all the real numbers so that each one can be encoded by a just pair base and value (or just nul for 0 since superposition of signals is not allowed). This is illustrated for various values on Fig. 8. Theorem 6 (Durand-Lose, 2007) AGC with finitely many signals and no singularity is equivalent to the linear BSS model.

Simulations have been established in both directions. In the constructions for SM simulation, the encoding pairs are manipulated so that they are clearly identified and everything is scaled down whenever they might mess up.

Theorem 7 (Durand-Lose, 2008a) With the Simple trace scheme (3 of Def. 4) for singularities, AGC is able to carry out any multiplication achieving the simulation of the whole BSS.

In this case AGC is strictly more powerful than classical BSS since square root can be computed.

Infinite analog computations

The meaning of the shrinking structure on a BM simulation is considered before entering into technical issues. 4.2.1 Interpretation. Assuming that everything works well as expected, the ESM can be made so that if the computation stops then some information leaves the singularity. But what kind of information? Usually it is considered that only finitely many values can be used3 , not countably many, not continuum many! Mechanisms as in Subsect. 3.2 can be used to send a few bits, but it is not clear how to send four signals (to encode a real number) ensuring that they are all at the same scale (i.e. are emitted from the same active region).

With the same construction as previously, using a universal BM, the BSS halting problem, can be decided. Let us consider another example. BSS machines can simulate any TM and any recursive function. There is a BM with one entry that tries all the rational numbers sequentially and stops if it is equal to the entry. Since halting can be decided, the characteristic function of Q is computable (which is not usually the case).

The general form of decision problems that can be solved is of the form ∃n ∈ N, φ(n, -→ X ) where φ is decision BM that stops for all entries. This definition is the same as the one for classical recursion except that total recursive predicate is replaced by total BSS predicate. The quantification is on N (that can encode Q or many other countable sets) but not on R. This does not correspond to the first and second level of an analytical hierarchy but an arithmetical one. It corresponds to BCSS-Σ 1 in [START_REF] Ziegler | Short) Survey of real hypercomputation[END_REF]. Please note that this is only a lower bound on the computing capability.

If one wants the analog output if the computation stops and just the information that is does not stop otherwise, it uses a singularity to know whether the computation stops and if it is the case, then it starts the computation normally to get the result in finite time.

If one would like to have the limit of say first cell of the array if any, not only does the shrinking might turn the scale and the distance between encoding signals to zero but moreover, if the BM-computation uses bigger and bigger real numbers, its accumulated re-scaling also turns them to zero. So that one would have to find how to generate the value in a way that does not lead to zero divided by zero and neither prevents the shrinking. This has been achieved to get internal multiplication out of linear BSS: three of the four real numbers encoding signals are constant outside of the singularity and the singularity happens at the correct position for the last signal. A general scheme still have to be found.

Technical issues.

In each active region, the configuration only undergoes a regular scaling. Up to scaling, the active regions perfectly assemble. The computation is exact and the real values are preserved even though the encoding can be split between various active regions (retrieving the value is not obvious).

The difference from the discrete case is that singularities are already used for multiplication. These are handled with the simple trace scheme (3 of Def. 4).

With the structure, both type of singularity should be distinguished particularly because the singularity for multiplication could happen exactly on toggle so that with the simple trace scheme, the structure would be damaged. In this case, one extra frozen meta-signal must exist to encode the singularity as well as a toggle for the structure. The case 4 -which is more general-is used. Since the speed of toggle is greater than the any of the other signal present for the multiplication, it gets straight into the singularity without getting involved in any collision and thus distinguishes between the singularities.

If there are infinitely many multiplications, then the singularity is of second order. This is not a problem for the structure nor the definition of space-time diagrams. Rule 4 of Def. 3 only asks for infinitely many collisions or signals which is also ensured by the accumulating multiplications.

Nested singularities

Previous Section ends with a second order singularity. It is possible to built higher order singularities.

Section 2.2 explains how to shrink any space-time diagram that has no singularity. It is quite easy to set signals to automatically start a singularity (in the spirit of what is done in Durand-Lose (2006b)) and according to the result to start another. There can be finitely or countably many isolated singularities (there is a rational location in each open).

The interesting part is when singularities are nested inside another one. In Sect. 4.2.2, it is explained how, with the conditional traces scheme (4 of Def. 4), to handle sub-singularities. The second order structure works because it is built on top of the previous one (after renaming the metasignals to avoid any conflict). So that the outer one can handle the inner ones while the latter proceed on their own.

It is thus natural to reiterate the construction. This can be done safely a finite number of times (more would yield an infinite number of signals). Inside any structure, it is only possible to start a lesser level structure so that the first one is the topmost and that the number of nested levels inside is bounded by construction of the ESM.

For discrete computations, in the setting presented in Subsect. 3.2, singularities are only used to decide and leave no trace (2 of Def. 4). But since a singularity could happen on a toggle of a higher level structure, for the same reason as before, the conditional traces scheme has to be used. For analog computations, this scheme is already used. It is thus the natural scheme to use in both cases.

In the discrete case, like for the SAD computers of Hogarth (1994,2004), each order brings the capability to decide an extra level of the arithmetical hierarchy by deciding an extra alternating quantifier (on N). As shown, first order decides Σ 0 1 . If nth order singularity allow to decided Σ 0 n , then it can be used as oracles inside the top level of a n + 1th order singularity.

In the analog case, each level of singularity identically allows to decide an extra alternation of quantifiers (on N) and to climb the BSS arithmetical hierarchy. This is not a quantification on R, this is not an algebraic hierarchy.

Conclusion

Abstract geometrical computation provides a setting where Black hole-like computation can be implemented: a finite portion is infinitely accelerated while a computation can continue outside and get a finite insight on what happens inside. For SAD computers, the (nested) black holes have to be found while in AGC the computation construct them (signals are the "fabric" of space and time) but the maximum level of nesting is limited by the construction of the ESM.

In our constructions, there are two levels of space-time: one absolute of the SM and one due to the embedding inside a shrinking structure; singularities are created by the fabric of signals. The following have been proved.

Theorem 8 With proper handling of accumulation, for any level of the arithmetic hierarchy, a rational ESM can be built to decide it and for any level of the BSS arithmetic hierarchy, an ESM can be built to decide it.

These are just decisions, but they can be used as sub-computations in any computation.

In the discrete case, the ESM and space-time-diagrams remain rational (irrational coordinate can only be generated as singularity location, but, by construction, the singularities built happen only at rational position).

A general construction that would allow all orders with the same ESM is still lacking. One important achievement would be to provide a system for transfinite order singularity together with the possibility to nest inside recursive computations. Considering spaces with more dimensions, could help getting hyper-arithmetic (Bournez, 1999a,b). But our scheme is only in one dimension, signals with dimension 1 or more could be used to shrunk in such spaces.

Definition 3

 3 The space-time diagram issued from an initial configuration c 0 and lasting for T , is a function c from [0, T ] to configurations (i.e. a function from R ×

Fig. 1

 1 Fig. 1 Freezing principle.

Fig. 2

 2 Fig. 2 Algorithm to add the freezing capability.

  Freeze, Scale and unfreeze.

Fig. 3

 3 Fig. 3 Scaling.

  Fig. 4 iterated scaling.

Fig. 5

 5 Fig. 5 Iterated scaling example.

  7

Fig. 7

 7 Fig.7Encapsulating the shrinking structure to retrieve any leaving signal.

Fig. 8

 8 Fig. 8 Encoding: scale and values -π, 0 and √ 2.

  There are various schemes to continue a space-time diagram at an isolated singularity. 1. Wall. It remains there forever; 2. Vanish. It disappears as if it where on another dimension; 3. Simple trace. It disappears but sends a µ s signal; or 4. Conditional traces. It disappears but sends signals according to which signals join in (i.e. signals that are not interrupted by any collision -not an infinite succession of signals).

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).

Comparing to infinite time Turing machine [START_REF] David | Infinite time Turing machines[END_REF][START_REF] David | Infinite time Turing machines: supertask computation[END_REF][START_REF] David | A survey of infinite time Turing machines[END_REF], the content of the tape is lost since it all accumulates in one point. So a way to preserve the resulting tape and a limit mechanism still have to be found to relate to infinite time Turing machines and recursive analysis [START_REF] Weihrauch | Introduction to computable analysis[END_REF]. The same problem arise with the analog counterpart; providing limits would link to the hierarchy of [START_REF] Chadzelek | Analytic machines[END_REF].