Logical Approaches to Computational Barriers

Abstract geometrical computation: beyond the Blum, Shub and Smale model with accumulation

Speaker:
| Jérôme Durand-Lose |

Slot: |
Array, 11:00-11:20, col. 5 |

Abstract geometrical computation (AGC) naturally arises as a continuous counterpart of cellular automata. It relies on signals (dimensionless points) traveling and colliding. It can carry out any (discrete) Turing-computation, but since it works with continuous time and space, some analog computing capability exists. In Abstract Geometrical Computation and the Linear BSS Model (CiE 2007, LNCS 4497, p. 238-247), it is shown that basic AGC has the same computing capability as the linear BSS. Using continuous space and time, it is possible to embed accumulations in AGC: infinitely many time steps in a finite duration. This has been used to implement the black-hole model of computation (Fundamenta Informaticae 74(4), p. 491-510). It also makes it possible to multiply two variables, thus simulating the full BSS. Nevertheless a BSS uncomputable function, the square root, can also be implemented, thus proving that the computing capability of AGC with accumulation is strictly beyond the one of BSS.

websites: Arnold Beckmann | 2008-06-14 |