Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Special Session Talk:
Computing by Observing

Edit abstract data

Speaker: Matteo Cavaliere

Abstract

A standard procedure in experimental sciences is to conduct an experiment,
observe its (entire) progress and then take the result of this observation as
the final output. A momentary picture of the observed system is irrelevant, and
rather the entire dynamics of the observed system is evaluated.   Motivated by
this, we have introduced a paradigm of computation where the output is obtained
by observing the entire trajectory of a system. 
The approach stresses the role of the observer in computation and has been
applied in the area of automata theory, formal languages and natural computing,
proving that "simple" experiments observed in a clever manner by
"simple" tools can compute that which much more complex processes can
compute.  
 In some cases one can obtain every possible computational device without
changing the observed system but only by finding the "correct"
external observer, with both - observed system and observer of limited
computational power.

 
References

M. Cavaliere, P. Leupold, Evolution and Observation - A Non Standard Way to
Generate Formal Languages, Theoretical Computer Science, 321, 2004.

M. Cavaliere,  P. Frisco, H.J. Hoogeboom, Computing by Only Observing, Tenth
Int. Conference on  Developments in Language Theory 2006, DLT2006, Santa
Barbara, CA, LNCS , 4036, Springer, 2006.

M. Cavaliere, P. Leupold, Evolution and Observation - A Non Standard Way to
Accept Formal Languages, Machines, Computations and Universality 2004, St.
Petersburg, Russia, LNCS 3354, Springer, 2005. Extended version in
Fundamenta Informaticae, 74, 4, 2006.

M. Cavaliere, N. Jonoska, P. Leupold, DNA Splicing: Computing by Observing,
Natural Computing, 2007.

 


websites: Arnold Beckmann 2008-03-20 Valid HTML 4.01! Valid CSS!