Computing by observing: Simple systems and simple observers
Computing by observing: Simple systems and simple observers
复制标题
通过观察进行计算：简单的系统和简单的观察者
DOI：
10.1016/j.tcs.2010.05.040
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Peter Leupold
中科院分区：
文献类型：
--
作者：
M. Cavaliere;Peter Leupold
我们综述并扩展了关于“通过观察进行计算”这一范式的工作。它的主要特征是，人们认为一个不断演变的系统的行为是计算的结果。为此，外部观察者记录了这一行为。通过这种方式，可以确定观察者和被观测系统之间的几个计算权衡。事实证明，当使用适当的观测器时，计算简单的系统的观察到的行为可能非常复杂。例如，具有常规观察者的受限版本的上下文无关文法足以获得计算完备性。作为这里给出的第二个实例，我们将观察者应用于贴纸系统，这是DNA计算的一个抽象模型。最后，我们介绍和研究了观察者只能读取被观测系统的一种测量(例如，质量或温度)的情况，以这种方式模拟了对真实物理系统的观测的局限性。最后，对本课题的研究前景进行了展望。
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.