Complexity through the Observation of Simple Systems

Details Complexity through the Observation of Simple Systems Complexity through the Observation of Simple Systems

2009-06-18

arxiv.org/abs/0906.3332v1

EPTCS 1, 2009, pp. 22-30

Computer Science

Computational Complexity

Scientific paper

10.4204/EPTCS.1.3

We survey 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 end an observer records this behavior. 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. Finally, some directions for further research are proposed.

Affiliated with

Also associated with

No associations

Rating

Complexity through the Observation of Simple Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Complexity through the Observation of Simple Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity through the Observation of Simple Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-725408