Physics – Condensed Matter
Scientific paper
1995-07-28
Physics
Condensed Matter
1 reference corrected, 1 reference added, minor changes in body of manuscript
Scientific paper
10.1103/PhysRevE.53.4477
In a variety of studies of dynamical systems, the edge of order and chaos has been singled out as a region of complexity. It was suggested by Wolfram, on the basis of qualitative behaviour of cellular automata, that the computational basis for modelling this region is the Universal Turing Machine. In this paper, following a suggestion of Crutchfield, we try to show that the Turing machine model may often be too powerful as a computational model to describe the boundary of order and chaos. In particular we study the region of the first accumulation of period doubling in unimodal and bimodal maps of the interval, from the point of view of language theory. We show that in relation to the ``extended'' Chomsky hierarchy, the relevant computational model in the unimodal case is the nested stack automaton or the related indexed languages, while the bimodal case is modeled by the linear bounded automaton or the related context-sensitive languages.
No associations
LandOfFree
The Computational Complexity of Symbolic Dynamics at the Onset of Chaos 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 The Computational Complexity of Symbolic Dynamics at the Onset of Chaos, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Computational Complexity of Symbolic Dynamics at the Onset of Chaos will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-679332