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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle 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\}.}$

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

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

${\displaystyle 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\}.}$

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

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

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

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

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

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

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

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

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

${\displaystyle 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\}.}$

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

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

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

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

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

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

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

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

${\displaystyle 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\},}$

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

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

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

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

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

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

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

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

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

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

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