Computing by observing: Simple systems and simple observers

Matteo Cavaliere, Peter Leupold

Research output: Chapter in Book/Report/Conference proceedingChapter (peer-reviewed)peer-review

Abstract / Description of output

We survey and extend the work on the paradigm called “computing by observing”. Its central feature is that one considers the behavior of an evolving system as the result of a computation. To this purpose an external observer records this behavior. In this way, several computational trade-offs between the observer and the observed system can be determined. It has turned out that the observed behavior of computationally simple systems can be very complex, when an appropriate observer is used. For example, a restricted version of context-free grammars with regular observers suffices to obtain computational completeness. As a second instantiation presented here, we apply an observer to sticker systems, an abstract model of DNA computing. Finally, we introduce and investigate the case where the observers can read only one measure of the observed system (e.g., mass or temperature), modeling in this way the limitations in the observation of real physical systems. Finally, a research perspective on the topic is presented.
Original languageEnglish
Title of host publicationComplexity of Simple Programs
PublisherTheoretical Computer Science
Number of pages10
Publication statusPublished - 2011


Dive into the research topics of 'Computing by observing: Simple systems and simple observers'. Together they form a unique fingerprint.

Cite this