Content deleted Content added
m →History: Journal cites:, added 1 PMID |
Reverted 1 edit by 2A00:1880:A008:5E7D:C8F4:311C:7E17:DCF2 (talk): Rv citespam |
||
| (20 intermediate revisions by 15 users not shown) | |||
Line 1:
{{Short description|Modeling a dynamical system's states as infinite sequences of symbols}}
In [[mathematics]], '''symbolic dynamics''' is the practice of modeling a topological or smooth [[dynamical system]] by a discrete space consisting of infinite [[sequence]]s of abstract symbols, each of which corresponds to a [[Dynamical system|state]] of the system, with the dynamics (evolution) given by the [[shift operator]]. Formally, a [[Markov partition]] is used to provide a [[finite cover]] for the smooth system; each set of the cover is associated with a single symbol, and the sequences of symbols result as a trajectory of the system moves from one covering set to another.▼
In [[mathematics]], '''symbolic dynamics''' is the study of dynamical systems defined on a discrete space consisting of infinite [[sequence]]s of abstract symbols. The evolution of the dynamical system is defined as a simple shift of the sequence.
▲
== History ==
The idea goes back to [[Jacques Hadamard]]'s 1898 paper on the [[geodesic]]s on [[surface (topology)|surface]]s of negative [[curvature]].<ref>{{cite journal |first=J. |last=Hadamard |title=Les surfaces à courbures opposées et leurs lignes géodésiques |journal=[[Journal de Mathématiques Pures et Appliquées|J. Math. Pures Appl.]] |volume=5 |issue=4 |year=1898 |pages=27–73 |url=http://sites.mathdoc.fr/JMPA/PDF/JMPA_1898_5_4_A3_0.pdf |language=fr}}</ref> It was applied by [[Marston Morse]] in 1921 to the construction of a nonperiodic recurrent geodesic. Related work was done by [[Emil Artin]] in 1924 (for the system now called [[Artin billiard]]), [[Pekka Myrberg]], [[Paul Koebe]], [[Jakob Nielsen (mathematician)|Jakob Nielsen]], [[G. A. Hedlund]].
The first formal treatment was developed by Morse and Hedlund in their 1938 paper.<ref>{{cite journal |jstor=2371264 |authorlink=Marston Morse |
[[Claude Shannon]] used symbolic sequences and [[shift of finite type|shifts of finite type]] in his 1948 paper ''[[A mathematical theory of communication]]'' that gave birth to [[information theory]].
During the late 1960s the method of symbolic dynamics was developed to [[Hyperbolic toral automorphism|hyperbolic toral automorphisms]] by [[Roy Adler]] and [[Benjamin Weiss]],<ref>{{Cite journal | title = Entropy, a complete metric invariant for automorphisms of the torus | journal = [[Proceedings of the National Academy of Sciences of the United States of America|PNAS]] | volume = 57| pages = 1573–1576 | year = 1967| last1 = Adler | first1 = R. | last2 = Weiss | first2 = B. | issue = 6 |jstor=57985 | bibcode = 1967PNAS...57.1573A | doi=10.1073/pnas.57.6.1573| pmc = 224513 | pmid=16591564| doi-access = free }}</ref> and to [[Anosov diffeomorphism]]s by [[Yakov Sinai]] who used the symbolic model to construct [[Gibbs measure]]s.<ref>{{Cite journal | title = Construction of Markov partitionings | journal = Funkcional. Anal.
A spectacular application of the methods of symbolic dynamics is [[Sharkovskii's theorem]] about [[periodic orbit]]s of a [[continuous map]] of an interval into itself (1964).
==Examples==
Consider the set of two-sided infinite sequences on two symbols, 0 and 1. A typical element in this set looks like: (..., 0, 1, 0, 0, 1, 0, 1, ... )
There will be exactly two fixed points under the shift map: the sequence of all zeroes, and the sequence of all ones. A periodic sequence will have a periodic orbit. For instance, the sequence (..., 0, 1, 0, 1, 0, 1, 0, 1, ...) will have period two.
More complex concepts such as [[heteroclinic orbit]]s and [[homoclinic orbit]]s also have simple descriptions in this system. For example, any sequence that has only a finite number of ones will have a homoclinic orbit, tending to the sequence of all zeros in forward and backward iterations.
===Itinerary===
Line 19 ⟶ 26:
== Applications ==
Symbolic dynamics originated as a method to study general dynamical systems; now its techniques and ideas have found significant applications in [[data storage device|data storage]] and [[data transmission|transmission]], [[linear algebra]], the motions of the planets and many other areas{{Citation needed|date=June 2021}}. The distinct feature in symbolic dynamics is that time is measured in ''[[discrete time|discrete]]'' intervals. So at each time interval the system is in a particular ''state''. Each state is associated with a symbol and the evolution of the system is described by an infinite [[sequence]] of symbols—represented effectively as [[String (computer science)|strings]]. If the system states are not inherently discrete, then the [[Quantum state|state vector]] must be discretized, so as to get a [[coarse-grained]] description of the system.
==See also==
* [[Measure-preserving dynamical system]]
* [[Combinatorics and dynamical systems]]
* [[Shift space]]
* [[Shift of finite type]]
* [[
* [[Arithmetic dynamics]]
Line 35 ⟶ 43:
| last = Hao
| first = Bailin
| authorlink =
| title = Elementary Symbolic Dynamics and Chaos in Dissipative Systems
| publisher = [[World Scientific]]
Line 45 ⟶ 52:
| doi =
| id =
| isbn = 9971-5-0682-3
| access-date = 2009-12-02
| archive-url = https://web.archive.org/web/20091205014855/http://power.itp.ac.cn/~hao/
| archive-date = 2009-12-05
| url-status = dead
}}
* Bruce Kitchens, ''Symbolic dynamics. One-sided, two-sided and countable state Markov shifts''. Universitext, [[Springer-Verlag]], Berlin, 1998. x+252 pp. {{isbn|3-540-62738-3}} {{MathSciNet|id=1484730}}
* {{cite book | first1=Douglas | last1=Lind | first2=Brian | last2=Marcus | title=An introduction to symbolic dynamics and coding | publisher=[[Cambridge University Press]] | year=1995 | isbn=0-521-55124-2 | zbl=1106.37301 | mr=1369092 | url=http://www.math.washington.edu/SymbolicDynamics/ | access-date=2005-06-03 | archive-date=2016-06-22 | archive-url=https://web.archive.org/web/20160622174208/http://www.math.washington.edu/SymbolicDynamics/ | url-status=dead }}
* G. A. Hedlund, ''[
* {{cite book| last = Teschl| given = Gerald|authorlink=Gerald Teschl| title = Ordinary Differential Equations and Dynamical Systems| publisher=[[American Mathematical Society]]| place = [[Providence, Rhode Island|Providence]]| year = 2012| isbn= 978-0-8218-8328-0| url =
*{{scholarpedia|title=Symbolic dynamics|urlname=Symbolic_dynamics}}
==External links==
* [http://chaosbook.org/ ChaosBook.org] Chapter "Transition graphs"
* [https://www.chaos-math.org/en/chaos-v-billiards.html A simulation of the three-bumper billiard system and its symbolic dynamics, from Chaos V: Duhem's Bull]
[[Category:Symbolic dynamics| ]]
| |||