Введение
Тип пространства сдвига, изучаемый в эргодической теории.
В математике, подсдвиги конечного типа используются для моделирования динамических систем и, в частности, являются объектами изучения в символической динамике и эргодической теории. Они также описывают множество всех возможных последовательностей, генерируемых машиной с конечным числом состояний. Наиболее широко изучаемыми пространствами сдвига являются подсдвиги конечного типа.
Примеры, которые побуждают
Рассмотрим ориентированный граф. (Односторонние) сдвиги конечного типа – это все последовательности, бесконечные только на одном конце, которые могут состоять из букв , как и (двусторонние) сдвиги конечного типа похожи, но бесконечны на обоих концах. Теперь, когда мы переходим к подмножеству подсдвигов, определяемому графом , мы ограничиваем переходы только теми, которые разрешены этим графом. Это дает нам только три возможных односторонних подсдвига. Аналогично, существует только три возможных двухсторонних подсдвига. Другие ориентированные графы над этими буквами дают другие подсдвиги. Например, если мы добавим еще одну стрелку , то вместо 3 у нас будет несчетно бесконечно много возможных подсдвигов.
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.
Терминология
Согласно условностям, термин "сдвиг" понимается как полный n-сдвиг. Подсдвиг — это любое подпространство полного сдвига, инвариантное относительно сдвига (то есть подпространство, которое остается неизменным при действии оператора сдвига), непустое и замкнутое относительно топологии произведения, определенной ниже. Некоторые подсдвиги можно характеризовать матрицей переходов, как указано выше; такие подсдвиги называются подсдвигами конечного типа. Часто подсдвиги конечного типа называют просто сдвигами конечного типа. Подсдвиги конечного типа также иногда называют топологическими сдвигами Маркова.
Примеры
Многие хаотические динамические системы изоморфны подшифтам конечного типа; примерами служат системы с поперечными гомоклиническими связями, диффеоморфизмы замкнутых многообразий с положительной метрической энтропией, система Пруэ–Тью–Морса, система Шакона (это первая система, показанная быть слабо смешивающей, но не сильно смешивающей), штурмовские системы и системы Топлица.
Обобщения
Софическая система — это образ подсдвига конечного типа, где различные рёбра графа переходов могут отображаться в один и тот же символ. Например, если наблюдать только выход скрытой цепи Маркова, то выход представляется софической системой. Её можно рассматривать как множество маркировок путей через автомат: поддвиг конечного типа соответствует детерминированному автомату. Такие системы соответствуют регулярным языкам. Контекстно-свободные системы определяются аналогичным образом и генерируются грамматиками структуры фраз. Система обновления определяется как множество всех бесконечных конкатенаций некоторой фиксированной конечной коллекции конечных слов. Подсдвиги конечного типа идентичны свободным (не взаимодействующим) одномерным моделям Поттса (n-буквенные обобщения моделей Изинга) с исключением определённых конфигураций ближайших соседей. Взаимодействующие модели Изинга определяются как поддвиги вместе с непрерывной функцией пространства конфигураций (непрерывной относительно топологии произведения, определяемой ниже); функция распределения и гамильтониан явно выражаются через эту функцию. Подсдвиги могут быть квантованы определённым образом, что приводит к идее квантовых конечных автоматов.
Метрическая
На пространстве сдвига можно определить множество различных метрик. Метрику на пространстве сдвига можно определить, считая две точки "близкими", если у них много совпадающих начальных символов; это p-адическая метрика. Фактически, и одностороннее, и двустороннее пространства сдвига являются компактными метрическими пространствами.