Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
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