Эргодикалық теориядағы ықшам кеңістік түрлері

Type of shift space studied in ergodic theory

In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. They also describe the set of all possible sequences executed by a finite state machine. The most widely studied shift spaces are the subshifts of finite type.

Consider a directed graph
The (one sided) shifts of finite type are all sequences, infinite on one end only, that can be made up of the letters , like The (two sided) shifts of finite type are similar, but are infinite on both ends. Now when we drop to the subset of subshifts, defined by the graph , we restrict transitions to only those allowed by the graph. This gives us only three possible one sided subshifts: Similarly, there are only three possible two sided subshifts. Other directed graphs on the letters give us other subshifts. For example, if we add another arrow , then instead of 3, we have uncountably infinitely many possible subshifts.

By convention, the term shift is understood to refer to the full n shift. A subshift is then any subspace of the full shift that is shift invariant (that is, a subspace that is invariant under the action of the shift operator), non empty, and closed for the product topology defined below. Some subshifts can be characterized by a transition matrix, as above; such subshifts are then called subshifts of finite type. Often, subshifts of finite type are called simply shifts of finite type. Subshifts of finite type are also sometimes called topological Markov shifts.

Many chaotic dynamical systems are isomorphic to subshifts of finite type; examples include systems with transverse homoclinic connections, diffeomorphisms of closed manifolds with a positive metric entropy, the Prouhet–Thue–Morse system, the Chacon system (this is the first system shown to be weakly mixing but not strongly mixing), Sturmian systems and Toeplitz systems.

A sofic system is an image of a subshift of finite type where different edges of the transition graph may be mapped to the same symbol. For example, if one only watches the output from a hidden Markov chain, then the output appears to be a sofic system. It may be regarded as the set of labellings of paths through an automaton: a subshift of finite type then corresponds to an automaton which is deterministic. Such systems correspond to regular languages. Context free systems are defined analogously, and are generated by phrase structure grammars. A renewal system is defined to be the set of all infinite concatenations of some fixed finite collection of finite words. Subshifts of finite type are identical to free (non interacting) one dimensional Potts models (n letter generalizations of Ising models), with certain nearest neighbor configurations excluded. Interacting Ising models are defined as subshifts together with a continuous function of the configuration space (continuous with respect to the product topology, defined below); the partition function and Hamiltonian are explicitly expressible in terms of this function. Subshifts may be quantized in a certain way, leading to the idea of the quantum finite automata.

A variety of different metrics can be defined on a shift space. One can define a metric on a shift space by considering two points to be "close" if they have many initial symbols in common; this is the p adic metric. In fact, both the one and two sided shift spaces are compact metric spaces.