Logical Approaches to Computational Barriers

Computing by Observing

Speaker:
| Matteo Cavaliere |

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 |