Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

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

Edit abstract data

Speaker: Jérôme Durand-Lose
Slot: Tue, 11:00-11:20, Room 19 (col. 5)

Abstract

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 Valid HTML 4.01! Valid CSS!