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. © 2010 Elsevier B.V. All rights reserved.

Computing by observing: Simple systems and simple observers / Cavaliere, M.; Leupold, P.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 412:1-2(2011), pp. 113-123. [10.1016/j.tcs.2010.05.040]

Computing by observing: Simple systems and simple observers

Cavaliere M.
;
2011

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. © 2010 Elsevier B.V. All rights reserved.
2011
412
1-2
113
123
Computing by observing: Simple systems and simple observers / Cavaliere, M.; Leupold, P.. - In: THEORETICAL COMPUTER SCIENCE. - ISSN 0304-3975. - 412:1-2(2011), pp. 113-123. [10.1016/j.tcs.2010.05.040]
Cavaliere, M.; Leupold, P.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Licenza Creative Commons
I metadati presenti in IRIS UNIMORE sono rilasciati con licenza Creative Commons CC0 1.0 Universal, mentre i file delle pubblicazioni sono rilasciati con licenza Attribuzione 4.0 Internazionale (CC BY 4.0), salvo diversa indicazione.
In caso di violazione di copyright, contattare Supporto Iris

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11380/1319963
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact