Сдвиг пространства

В символической динамике и смежных разделах математики пространство сдвига или подсдвиг представляет собой набор бесконечных слов , которые представляют собой эволюцию дискретной системы . Фактически, пространства сдвига и символические динамические системы часто считаются синонимами . Наиболее широко изученными пространствами сдвигов являются подсдвиги конечного типа и софик-сдвиги .

В классических рамках пространство сдвига — это любое подмножество $\Lambda$ из $A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}$, где $A$ — конечное множество, замкнутое для тихоновской топологии и инвариантное относительно сдвигов. В более общем смысле можно определить пространство сдвига как замкнутое и трансляционно-инвариантное подмножество $A^{\mathbb {G} }$, где $A$ любое непустое множество и $\mathbb {G}$ это любой моноид .

Определение

Позволять $\mathbb {G}$ быть моноидом , и учитывая $g,h\in \mathbb {G}$, обозначаем операцию $g$ с $h$ по продукту $gh$. Позволять $\mathbf {1} _{\mathbb {G} }$ обозначают личность $\mathbb {G}$. Рассмотрим непустое множество $A$ (алфавит) с дискретной топологией и определим $A^{\mathbb {G} }$ как набор всех шаблонов $A$ индексируется $\mathbb {G}$. Для $\mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }$ и подмножество $N\subset \mathbb {G}$, обозначим ограничение $\mathbf {x}$ к индексам $N$ как $\mathbf {x} _{N}:=(x_{i})_{i\in N}$.

На $A^{\mathbb {G} }$, мы рассматриваем продискретную топологию, что делает $A^{\mathbb {G} }$ Хаусдорфово и полностью несвязное топологическое пространство. В случае $A$ будучи конечным, отсюда следует, что $A^{\mathbb {G} }$ компактен. Однако, если $A$ не конечно, то $A^{\mathbb {G} }$ не является даже локально компактным.

Эта топология будет метризуемой тогда и только тогда, когда $\mathbb {G}$ счетна, и в любом случае база этой топологии состоит из набора открытых/замкнутых множеств (называемых цилиндрами), определенных следующим образом: учитывая конечный набор индексов $D\subset \mathbb {G}$, и для каждого $i\in D$, позволять $a_{i}\in A$. Цилиндр , заданный $D$ и $(a_{i})_{i\in D}\in A^{|D|}$ это набор

${\big [}(a_{i})_{i\in D}{\big ]}_{D}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ x_{i}=a_{i},\ \forall i\in D\}.$

Когда $D=\{g\}$, обозначим цилиндр, фиксирующий символ $b$ в записи, индексированной $g$ просто как $[b]_{g}$.

Другими словами, цилиндр ${\big [}(a_{i})_{i\in D}{\big ]}_{D}$ — это множество всего множества всех бесконечных шаблонов $A^{\mathbb {G} }$ которые содержат конечный шаблон $(a_{i})_{i\in D}\in A^{|D|}$.

Данный $g\in \mathbb {G}$, карта g -сдвига на $A^{\mathbb {G} }$ обозначается $\sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }$ и определяется как

$\sigma ^{g}{\big (}(x_{i})_{i\in \mathbb {G} }{\big )}=(x_{gi})_{i\in \mathbb {G} }$.

Пространство сдвига над алфавитом $A$ это набор $\Lambda \subset A^{\mathbb {G} }$ замкнутый по топологии $A^{\mathbb {G} }$ и инвариантен относительно трансляций, т.е. $\sigma ^{g}(\Lambda )\subset \Lambda$ для всех $g\in \mathbb {G}$. Рассмотрим в пространстве сдвига $\Lambda$ индуцированная топология из $A^{\mathbb {G} }$, который имеет в качестве основных открытых наборов цилиндры ${\big [}(a_{i})_{i\in D}{\big ]}_{\Lambda }:={\big [}(a_{i})_{i\in D}{\big ]}\cap \Lambda$.

Для каждого $k\in \mathbb {N} ^{*}$, определять ${\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}$, и ${\mathcal {N}}_{A^{\mathbb {G} }}^{f}:=\bigcup _{k\in \mathbb {N} }{\mathcal {N}}_{k}=\bigcup _{N\subset \mathbb {G} \atop \#N<\infty }A^{N}$. Эквивалентный способ определить пространство сдвига — взять набор запрещенных шаблонов. $F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}$ и определим пространство сдвига как набор

$X_{F}:=\{\mathbf {x} \in A^{\mathbb {G} }:\ \forall N\subset \mathbb {G} ,\forall g\in \mathbb {G} ,\ \left(\sigma ^{g}(\mathbf {x} )\right)_{N}=\mathbf {x} _{gN}\notin F\}.$

Интуитивно, пространство сдвига $X_{F}$ — это набор всех бесконечных шаблонов, которые не содержат ни одного запрещенного конечного шаблона $F$.

Язык пространства смены

Учитывая место смены $\Lambda \subset A^{\mathbb {G} }$ и конечное множество индексов $N\subset \mathbb {G}$, позволять $W_{\emptyset }(\Lambda ):=\{\epsilon \}$, где $\epsilon$ означает пустое слово, а $N\neq \emptyset$ позволять $W_{N}(\Lambda )\subset A^{N}$ — множество всех конечных конфигураций $A^{N}$ которые появляются в некоторой последовательности $\Lambda$, то есть,

$W_{N}(\Lambda ):=\{(w_{i})_{i\in N}\in A^{N}:\ \exists \ \mathbf {x} \in \Lambda {\text{ s.t. }}x_{i}=w_{i}\ \forall i\in N\}.$

Обратите внимание, что, поскольку $\Lambda$ является пространством сдвига, если $M\subset \mathbb {G}$ это перевод $N\subset \mathbb {G}$, то есть, $M=gN$ для некоторых $g\in \mathbb {G}$, затем $(w_{j})_{j\in M}\in W_{M}(\Lambda )$ тогда и только тогда, когда существует $(v_{i})_{i\in N}\in W_{N}(\Lambda )$ такой, что $w_{j}=v_{i}$ если $j=gi$. Другими словами, $W_{M}(\Lambda )$ и $W_{N}(\Lambda )$ содержат одинаковые конфигурации по модулю перевода. Мы вызовем набор

$W(\Lambda ):=\bigcup _{N\subset \mathbb {G}  \atop \#N<\infty }W_{N}(\Lambda )$

язык ​ ​ $\Lambda$. В общем контексте, изложенном здесь, язык пространства сдвига имеет не то же значение, что в формальной теории языка , но в классической структуре , которая рассматривает алфавит $A$ быть конечным, и $\mathbb {G}$ существование $\mathbb {N}$ или $\mathbb {Z}$ с обычным дополнением язык пространства сдвигов является формальным языком.

Классическая структура

Классическая структура пространств сдвигов состоит в рассмотрении алфавита $A$ как конечное, и $\mathbb {G}$ как набор неотрицательных целых чисел ( $\mathbb {N}$) с обычным сложением, или набор всех целых чисел ( $\mathbb {Z}$) с обычным дополнением. В обоих случаях идентификационный элемент $\mathbf {1} _{\mathbb {G} }$ соответствует числу 0. Кроме того, когда $\mathbb {G} =\mathbb {N}$, поскольку все $\mathbb {N} \setminus \{0\}$ может быть сгенерирован из числа 1, достаточно рассмотреть уникальную карту сдвига, заданную формулой $\sigma (\mathbf {x} )_{n}=x_{n+1}$ для всех $n$. С другой стороны, для случая $\mathbb {G} =\mathbb {Z}$, поскольку все $\mathbb {Z}$ можно сгенерировать из чисел {-1, 1}, достаточно рассмотреть две карты сдвига, заданные для всех $n$ к $\sigma (\mathbf {x} )_{n}=x_{n+1}$ и по $\sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}$.

Более того, всякий раз, когда $\mathbb {G}$ является $\mathbb {N}$ или $\mathbb {Z}$ с обычным сложением (независимо от мощности $A$), в силу своей алгебраической структуры достаточно рассматривать только цилиндры вида

$[a_{0}a_{1}...a_{n}]:=\{(x_{i})_{i\in \mathbb {G} }:\ x_{i}=a_{i}\ \forall i=0,..,n\}.$

Более того, язык пространства сдвига $\Lambda \subset A^{\mathbb {G} }$ будет предоставлен

$W(\Lambda ):=\bigcup _{n\geq 0}W_{n}(\Lambda ),$

где $W_{0}:=\{\epsilon \}$ и $\epsilon$ означает пустое слово, а

$W_{n}(\Lambda ):=\{((a_{i})_{i=0,..n}\in A^{n}:\ \exists \mathbf {x} \in \Lambda \ s.t.\ x_{i}=a_{i}\ \forall i=0,...,n\}.$

Аналогично, для частного случая $\mathbb {G} =\mathbb {Z}$, отсюда следует, что для определения пространства сдвига $\Lambda =X_{F}$ нам не нужно указывать индекс $\mathbb {G}$ на котором запрещенные слова $F$ определены, то есть мы можем просто рассматривать $F\subset \bigcup _{n\geq 1}A^{n}$ а потом

$X_{F}=\{\mathbb {x} \in A^{\mathbb {Z} }:\ \forall i\in \mathbb {Z} ,\ \forall k\geq 0,\ (x_{i}...x_{i+k})\notin F\}.$

Однако, если $\mathbb {G} =\mathbb {N}$, если мы определим пространство сдвига $\Lambda =X_{F}$ как и выше, без указания индекса того, где слова запрещены, мы просто захватим пространства сдвига, которые инвариантны для карты сдвига, то есть такие, что $\sigma (X_{F})=X_{F}$. Фактически, чтобы определить пространство сдвига $X_{F}\subset A^{\mathbb {N} }$ такой, что $\sigma (X_{F})\subsetneq X_{F}$ необходимо будет указать, с какого индекса на словах $F$ запрещены.

В частности, в классической схеме $A$ быть конечным, и $\mathbb {G}$ существование $\mathbb {N}$) или $\mathbb {Z}$ с обычным сложением отсюда следует, что $M_{F}$ конечно тогда и только тогда, когда $F$ конечно, что приводит к классическому определению сдвига конечного типа как пространства сдвига $\Lambda \subset A^{\mathbb {G} }$ такой, что $\Lambda =X_{F}$ для некоторого конечного $F$.

Некоторые типы сменных помещений

Среди нескольких типов пространств сдвигов наиболее широко изучены сдвиги конечного типа и софические сдвиги .

В случае, когда алфавит $A$ конечно, пространство сдвига $\Lambda$ является сдвигом конечного типа , если мы можем взять конечный набор запрещенных шаблонов $F$ такой, что $\Lambda =X_{F}$, и $\Lambda$ является софическим сдвигом, если он является образом сдвига конечного типа под действием скользящего блочного кода (то есть карта $\Phi$ непрерывно и инвариантно для всех $g$-сдвиг карты). Если $A$ конечно и $\mathbb {G}$ является $\mathbb {N}$ или $\mathbb {Z}$ с обычным сложением, затем сдвигом $\Lambda$ является софическим сдвигом тогда и только тогда, когда $W(\Lambda )$ это обычный язык .

Название «софик» было придумано Вайсом (1973) на основе еврейского слова סופי, означающего «конечный», для обозначения того факта, что это обобщение свойства конечности.

Когда $A$ бесконечно, можно определить сдвиги конечного типа как пространства сдвигов $\Lambda$ для тех можно взять набор $F$ запрещенных слов, таких, что

$M_{F}:=\{g\in \mathbb {G} :\ \exists N\subset \mathbb {G} {\text{ s.t. }}g\in N{\text{ and }}(w_{i})_{i\in N}\in F\},$

конечно и $\Lambda =X_{F}$. В контексте бесконечного алфавита софикационный сдвиг будет определяться как образ сдвига конечного типа в определенном классе скользящих блочных кодов . Оба, конечность $M_{F}$ и дополнительные условия скользящих блочных кодов тривиально выполняются всякий раз, когда $A$ конечно.

Топологические динамические системы в пространствах сдвига

Пространства сдвига — это топологические пространства , на которых символические динамические системы обычно определяются .

Учитывая место смены $\Lambda \subset A^{\mathbb {G} }$ и $g$-сдвиг карты $\sigma ^{g}:\Lambda \to \Lambda$ следует, что пара $(\Lambda ,\sigma ^{g})$ является топологической динамической системой .

Две смены $\Lambda \subset A^{\mathbb {G} }$ и $\Gamma \subset B^{\mathbb {G} }$ называются топологически сопряженными (или просто сопряженными), если для каждого $g$-карта сдвига, то топологические динамические системы $(\Lambda ,\sigma ^{g})$ и $(\Gamma ,\sigma ^{g})$ , топологически сопряжены то есть если существует непрерывное отображение $\Phi :\Lambda \to \Gamma$ такой, что $\Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi$. Такие отображения известны как обобщенные скользящие блочные коды или просто скользящие блочные коды, когда $\Phi$ является равномерно непрерывным.

Хотя любое непрерывное отображение $\Phi$ от $\Lambda \subset A^{\mathbb {G} }$ себе будет определять топологическую динамическую систему $(\Lambda ,\Phi )$, в символической динамике принято рассматривать только непрерывные отображения $\Phi :\Lambda \to \Lambda$ которые ездят со всеми $g$-сдвиговые карты, т.е. карты, которые представляют собой обобщенные скользящие блочные коды. Динамическая система $(\Lambda ,\Phi )$ известен как « обобщенный клеточный автомат » (или просто как клеточный автомат, когда $\Phi$ равномерно непрерывен).

Примеры

Первый тривиальный пример пространства сдвигов (конечного типа) — полный сдвиг $A^{\mathbb {N} }$.

Позволять $A=\{a,b\}$. Множество всех бесконечных слов над A, содержащих не более одного b, представляет собой софический подсдвиг не конечного типа. Множество всех бесконечных слов над A которых , b образуют блоки простой длины, не является софическим (это можно показать с помощью леммы о накачке ).

Пространство бесконечных струн в двух буквах, $\{0,1\}^{\mathbb {N} }$ называется процессом Бернулли . Оно изоморфно множеству Кантора .

Бибесконечное пространство строк из двух букв, $\{0,1\}^{\mathbb {Z} }$ широко известна как карта Бейкера или, скорее, гомоморфна карте Бейкера.

См. также

• Карта палаток
• Карта битового сдвига
• Код Грея

Дальнейшее чтение

• Чекерини-Зильберштейн, Т.; Коорнарт, М. (2010). Клеточные автоматы и группы Монографии Спрингера по математике . Спрингер Верлаг. ISBN  978-3-642-14034-1 .
• Линд, Дуглас; Маркус, Брайан (1995). Введение в символическую динамику и кодирование . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-55900-6 .
• Лотер, М. (2002). «Конечные и бесконечные слова» . Алгебраическая комбинаторика слов . Кембридж, Великобритания: Издательство Кембриджского университета. ISBN  0-521-81220-8 . Проверено 29 января 2008 г.
• Морс, Марстон ; Хедлунд, Густав А. (1938). «Символическая динамика». Американский журнал математики . 60 (4): 815–866. дои : 10.2307/2371264 . JSTOR   2371264 .
• Соботтка, М. (2022). «Некоторые заметки о классификации пространств сдвига: сдвиги конечного типа; софические сдвиги; и конечно определенные сдвиги». Бюллетень Бразильского математического общества . Новая серия. 53 (3): 981–1031. arXiv : 2010.10595 . дои : 10.1007/s00574-022-00292-x . S2CID   254048586 .