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

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
Pages113-123
Number of pages10
Volume412
DOIs
Publication statusPublished - 2011

Fingerprint

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

Cite this