Espacio de cambio

En dinámica simbólica y ramas afines de las matemáticas , un espacio de desplazamiento o subdesplazamiento es un conjunto de palabras infinitas que representan la evolución de un sistema discreto . De hecho, los espacios de desplazamiento y los sistemas dinámicos simbólicos suelen considerarse sinónimos . Los espacios de desplazamiento más estudiados son los subdesplazamientos de tipo finito y los desplazamientos sóficos .

En el marco clásico ^{[ 1 ]} un espacio de desplazamiento es cualquier subconjunto${\displaystyle \Lambda }$de${\displaystyle A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}}$, dónde${\displaystyle A}$es un conjunto finito , que es cerrado para la topología de Tychonov e invariante por traslaciones. De manera más general, se puede definir un espacio de desplazamiento como los subconjuntos cerrados e invariantes por traslaciones de${\displaystyle A^{\mathbb {G} }}$, dónde${\displaystyle A}$es cualquier conjunto no vacío y${\displaystyle \mathbb {G} }$es cualquier monoide . ^{[ 2 ] [ 3 ]}

Dejar${\displaystyle \mathbb {G} }$sea ​​un monoide y dado${\displaystyle g,h\in \mathbb {G} }$, denotan la operación de${\displaystyle g}$con${\displaystyle h}$por el producto${\displaystyle gh}$. Dejar${\displaystyle \mathbf {1} _{\mathbb {G} }}$denotan la identidad de${\displaystyle \mathbb {G} }$Consideremos un conjunto no vacío.${\displaystyle A}$(un alfabeto) con la topología discreta , y definir${\displaystyle A^{\mathbb {G} }}$como el conjunto de todos los patrones sobre${\displaystyle A}$indexado por${\displaystyle \mathbb {G} }$. Para${\displaystyle \mathbf {x} =(x_{i})_{i\in \mathbb {G} }\in A^{\mathbb {G} }}$y un subconjunto${\displaystyle N\subset \mathbb {G} }$, denotamos la restricción de${\displaystyle \mathbf {x} }$a los índices de${\displaystyle N}$como${\displaystyle \mathbf {x} _{N}:=(x_{i})_{i\in N}}$.

En${\displaystyle A^{\mathbb {G} }}$, consideramos la topología prodiscreta , que hace${\displaystyle A^{\mathbb {G} }}$un espacio topológico de Hausdorff y totalmente desconectado . En el caso de${\displaystyle A}$Siendo finito, se deduce que${\displaystyle A^{\mathbb {G} }}$es compacto . Sin embargo, si${\displaystyle A}$no es finito, entonces${\displaystyle A^{\mathbb {G} }}$Ni siquiera es compacto localmente.

Esta topología será metrizable si y solo si${\displaystyle \mathbb {G} }$es contable y, en cualquier caso, la base de esta topología consiste en una colección de conjuntos abiertos/cerrados (llamados cilindros), definidos de la siguiente manera: dado un conjunto finito de índices${\displaystyle D\subset \mathbb {G} }$y para cada uno${\displaystyle i\in D}$, dejar${\displaystyle a_{i}\in A}$. El cilindro dado por${\displaystyle D}$y${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$es el conjunto

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

Cuando${\displaystyle D=\{g\}}$, denotamos el cilindro que fija el símbolo${\displaystyle b}$en la entrada indexada por${\displaystyle g}$simplemente como${\displaystyle [b]_{g}}$.

En otras palabras, un cilindro${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{D}}$es el conjunto de todos los conjuntos de todos los patrones infinitos de${\displaystyle A^{\mathbb {G} }}$que contienen el patrón finito${\displaystyle (a_{i})_{i\in D}\in A^{|D|}}$.

Dado${\displaystyle g\in \mathbb {G} }$, el mapa de desplazamiento g en${\displaystyle A^{\mathbb {G} }}$se denota por${\displaystyle \sigma ^{g}:A^{\mathbb {G} }\to A^{\mathbb {G} }}$y definido como

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

Un espacio de desplazamiento sobre el alfabeto${\displaystyle A}$es un conjunto${\displaystyle \Lambda \subset A^{\mathbb {G} }}$que está cerrado bajo la topología de${\displaystyle A^{\mathbb {G} }}$y invariante bajo traslaciones, es decir,${\displaystyle \sigma ^{g}(\Lambda )\subset \Lambda }$a pesar de${\displaystyle g\in \mathbb {G} }$. ^{[ nota 1 ]} Consideramos en el espacio de desplazamiento${\displaystyle \Lambda }$la topología inducida a partir de${\displaystyle A^{\mathbb {G} }}$, que tiene como conjuntos abiertos básicos los cilindros${\displaystyle {\big [}(a_{i})_{i\in D}{\big ]}_{\Lambda }:={\big [}(a_{i})_{i\in D}{\big ]}\cap \Lambda }$.

Para cada${\displaystyle k\in \mathbb {N} ^{*}}$, definir${\displaystyle {\mathcal {N}}_{k}:=\bigcup _{N\subset \mathbb {G} \atop \#N=k}A^{N}}$, y${\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}}$Una forma equivalente de definir un espacio de desplazamiento es tomar un conjunto de patrones prohibidos.${\displaystyle F\subset {\mathcal {N}}_{A^{\mathbb {G} }}^{f}}$y definir un espacio de desplazamiento como el conjunto

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

Intuitivamente, un espacio de cambio${\displaystyle X_{F}}$es el conjunto de todos los patrones infinitos que no contienen ningún patrón finito prohibido de${\displaystyle F}$.

Dado un espacio de cambio${\displaystyle \Lambda \subset A^{\mathbb {G} }}$y un conjunto finito de índices${\displaystyle N\subset \mathbb {G} }$, dejar${\displaystyle W_{\emptyset }(\Lambda ):=\{\epsilon \}}$, dónde${\displaystyle \epsilon }$representa la palabra vacía y para${\displaystyle N\neq \emptyset }$dejar ${\displaystyle W_{N}(\Lambda )\subset A^{N}}$sea ​​el conjunto de todas las configuraciones finitas de${\displaystyle A^{N}}$que aparecen en alguna secuencia de${\displaystyle \Lambda }$, es decir,

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

Tenga en cuenta que, dado que${\displaystyle \Lambda }$es un espacio de desplazamiento, si${\displaystyle M\subset \mathbb {G} }$es una traducción de${\displaystyle N\subset \mathbb {G} }$, es decir,${\displaystyle M=gN}$para algunos${\displaystyle g\in \mathbb {G} }$, entonces${\displaystyle (w_{j})_{j\in M}\in W_{M}(\Lambda )}$si y solo si existe${\displaystyle (v_{i})_{i\in N}\in W_{N}(\Lambda )}$de tal manera que${\displaystyle w_{j}=v_{i}}$si${\displaystyle j=gi}$. En otras palabras,${\displaystyle W_{M}(\Lambda )}$y${\displaystyle W_{N}(\Lambda )}$contienen las mismas configuraciones módulo traslación. Llamaremos al conjunto

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

el idioma de${\displaystyle \Lambda }$En el contexto general aquí expuesto, el lenguaje de un espacio de desplazamiento no tiene el mismo significado que en la Teoría del Lenguaje Formal , sino en el marco clásico que considera el alfabeto.${\displaystyle A}$siendo finito, y${\displaystyle \mathbb {G} }$ser${\displaystyle \mathbb {N} }$o${\displaystyle \mathbb {Z} }$Con la salvedad habitual, el lenguaje de un espacio de desplazamiento es un lenguaje formal.

El marco clásico para los espacios de desplazamiento consiste en considerar el alfabeto${\displaystyle A}$como finito, y${\displaystyle \mathbb {G} }$como el conjunto de enteros no negativos (${\displaystyle \mathbb {N} }$) con la suma habitual, o el conjunto de todos los enteros (${\displaystyle \mathbb {Z} }$) con la adición habitual. En ambos casos, el elemento identidad${\displaystyle \mathbf {1} _{\mathbb {G} }}$corresponde al número 0. Además, cuando${\displaystyle \mathbb {G} =\mathbb {N} }$, ya que todos${\displaystyle \mathbb {N} \setminus \{0\}}$puede generarse a partir del número 1, es suficiente considerar un mapa de desplazamiento único dado por${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$a pesar de${\displaystyle n}$Por otro lado, en el caso de${\displaystyle \mathbb {G} =\mathbb {Z} }$, ya que todos${\displaystyle \mathbb {Z} }$se puede generar a partir de los números {-1, 1}, es suficiente considerar dos mapas de desplazamiento dados para todos${\displaystyle n}$por${\displaystyle \sigma (\mathbf {x} )_{n}=x_{n+1}}$y por${\displaystyle \sigma ^{-1}(\mathbf {x} )_{n}=x_{n-1}}$.

Además, siempre que${\displaystyle \mathbb {G} }$es${\displaystyle \mathbb {N} }$o${\displaystyle \mathbb {Z} }$con la adición habitual (independientemente de la cardinalidad de ${\displaystyle A}$), debido a su estructura algebraica, basta con considerar únicamente cilindros en la forma

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

Además, el lenguaje de un espacio de cambio ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$será dado por

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

dónde${\displaystyle W_{0}:=\{\epsilon \}}$y${\displaystyle \epsilon }$representa la palabra vacía, y

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

De la misma manera, para el caso particular de${\displaystyle \mathbb {G} =\mathbb {Z} }$, de ello se deduce que para definir un espacio de desplazamiento${\displaystyle \Lambda =X_{F}}$no necesitamos especificar el índice de${\displaystyle \mathbb {G} }$en las cuales las palabras prohibidas de${\displaystyle F}$están definidos, es decir, podemos simplemente considerar ${\displaystyle F\subset \bigcup _{n\geq 1}A^{n}}$y luego

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

Sin embargo, si${\displaystyle \mathbb {G} =\mathbb {N} }$, si definimos un espacio de desplazamiento${\displaystyle \Lambda =X_{F}}$como arriba, sin especificar el índice donde las palabras están prohibidas, entonces simplemente capturaremos espacios de desplazamiento que son invariantes a través del mapa de desplazamiento, es decir, tales que${\displaystyle \sigma (X_{F})=X_{F}}$. De hecho, para definir un espacio de desplazamiento${\displaystyle X_{F}\subset A^{\mathbb {N} }}$de tal manera que${\displaystyle \sigma (X_{F})\subsetneq X_{F}}$será necesario especificar de qué índice en las palabras de${\displaystyle F}$están prohibidos.

En particular, en el marco clásico de${\displaystyle A}$siendo finito, y${\displaystyle \mathbb {G} }$ser${\displaystyle \mathbb {N} }$) o${\displaystyle \mathbb {Z} }$Con la adición habitual, se deduce que${\displaystyle M_{F}}$es finito si y solo si${\displaystyle F}$es finito, lo que lleva a la definición clásica de un desplazamiento de tipo finito como esos espacios de desplazamiento${\displaystyle \Lambda \subset A^{\mathbb {G} }}$de tal manera que${\displaystyle \Lambda =X_{F}}$para algún finito${\displaystyle F}$.

Entre los diversos tipos de espacios de desplazamiento, los más estudiados son los desplazamientos de tipo finito y los desplazamientos sóficos .

En el caso de que el alfabeto${\displaystyle A}$es finito, un espacio de desplazamiento${\displaystyle \Lambda }$es un cambio de tipo finito si podemos tomar un conjunto finito de patrones prohibidos${\displaystyle F}$de tal manera que${\displaystyle \Lambda =X_{F}}$, y${\displaystyle \Lambda }$es un desplazamiento sófico si es la imagen de un desplazamiento de tipo finito bajo código de bloque deslizante ^{[ 1 ]} (es decir, un mapa${\displaystyle \Phi }$que es continuo e invariante para todos${\displaystyle g}$-mapas de desplazamiento). Si${\displaystyle A}$es finito y${\displaystyle \mathbb {G} }$es${\displaystyle \mathbb {N} }$o${\displaystyle \mathbb {Z} }$con la adición habitual, luego el cambio${\displaystyle \Lambda }$es un cambio sófico si y solo si${\displaystyle W(\Lambda )}$es un lenguaje regular .

El nombre "sofic" fue acuñado por Weiss (1973) , basado en la palabra hebrea סופי que significa " finito " , para referirse al hecho de que se trata de una generalización de una propiedad de finitud. ^{[ 4 ]}

Cuando${\displaystyle A}$es infinito, es posible definir desplazamientos de tipo finito como espacios de desplazamiento${\displaystyle \Lambda }$para aquellos uno puede tomar un conjunto${\displaystyle F}$de palabras prohibidas tales que $${\displaystyle M_{F}:=\{g\in \mathbb {G}$$ :\ \exists N\subset \mathbb {G} {\text{ st }}g\in N{\text{ y }}(w_{i})_{i\in N}\in F\}} es finito y${\displaystyle \Lambda =X_{F}}$. ^{[ 3 ]} En este contexto de alfabeto infinito, un desplazamiento sófico se definirá como la imagen de un desplazamiento de tipo finito bajo una clase particular de códigos de bloques deslizantes . ^{[ 3 ]} Tanto la finitud de${\displaystyle M_{F}}$y las condiciones adicionales de los códigos de bloque deslizante se satisfacen trivialmente siempre que${\displaystyle A}$es finito.

Los espacios de desplazamiento son los espacios topológicos sobre los que se suelen definir los sistemas dinámicos simbólicos .

Dado un espacio de cambio${\displaystyle \Lambda \subset A^{\mathbb {G} }}$y un${\displaystyle g}$-mapa de desplazamiento${\displaystyle \sigma ^{g}:\Lambda \to \Lambda }$De ello se deduce que la pareja${\displaystyle (\Lambda ,\sigma ^{g})}$es un sistema dinámico topológico .

Dos espacios de turno${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ y${\displaystyle \Gamma \subset B^{\mathbb {G} }}$ Se dice que son topológicamente conjugados (o simplemente conjugados) si para cada${\displaystyle g}$-mapa de desplazamiento se deduce que los sistemas dinámicos topológicos${\displaystyle (\Lambda ,\sigma ^{g})}$y${\displaystyle (\Gamma ,\sigma ^{g})}$son topológicamente conjugados , es decir, si existe un mapa continuo${\displaystyle \Phi$ :\Lambda \to \Gamma } tal que ${\displaystyle \Phi \circ \sigma ^{g}=\sigma ^{g}\circ \Phi }$Dichos mapas se conocen como códigos de bloques deslizantes generalizados o simplemente como códigos de bloques deslizantes cuando${\displaystyle \Phi }$es uniformemente continua. ^{[ 3 ]}

Aunque cualquier mapa continuo${\displaystyle \Phi }$de${\displaystyle \Lambda \subset A^{\mathbb {G} }}$por sí mismo definirá un sistema dinámico topológico.${\displaystyle (\Lambda ,\Phi )}$En dinámica simbólica, es habitual considerar únicamente mapas continuos.${\displaystyle \Phi$ :\Lambda \to \Lambda } que conmutan con todos${\displaystyle g}$Mapas de desplazamiento, es decir, mapas que son códigos de bloques deslizantes generalizados. El sistema dinámico${\displaystyle (\Lambda ,\Phi )}$se conoce como un ' autómata celular generalizado ' (o simplemente como un autómata celular cuando${\displaystyle \Phi }$es uniformemente continua).

El primer ejemplo trivial de espacio de desplazamiento (de tipo finito) es el desplazamiento completo.${\displaystyle A^{\mathbb {N} }}$.

Dejar${\displaystyle A=\{a,b\}}$El conjunto de todas las palabras infinitas sobre A que contienen como máximo una b es un subdesplazamiento sófico, no de tipo finito. El conjunto de todas las palabras infinitas sobre A cuya b forman bloques de longitud prima no es sófico (esto se puede demostrar utilizando el lema de bombeo ).

El espacio de cadenas infinitas en dos letras,${\displaystyle \{0,1\}^{\mathbb {N} }}$Se denomina proceso de Bernoulli . Es isomorfo al conjunto de Cantor .

El espacio bi-infinito de cadenas en dos letras,${\displaystyle \{0,1\}^{\mathbb {Z} }}$es comúnmente conocido como el mapa de Baker , o más bien es homomorfo al mapa de Baker.

• Mapa de la tienda de campaña
• Mapa de desplazamiento de bits
• Código gris

• Ceccherini-Silberstein, T.; Coornaert, M. (2010). Autómatas celulares y grupos. Springer Monographs in Mathematics . Springer Verlag. ISBN 978-3-642-14034-1.
• Lind, Douglas; Marcus, Brian (1995). Introducción a la dinámica simbólica y la codificación . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-55900-6.
• Lothaire, M. (2002). «Palabras finitas e infinitas» . Combinatoria algebraica sobre palabras . Cambridge, Reino Unido: Cambridge University Press. ISBN 0-521-81220-8. Consultado el 29 de enero de 2008 .
• Morse, Marston ; Hedlund, Gustav A. (1938). "Dinámica simbólica". American Journal of Mathematics . 60 (4): 815– 866. doi : 10.2307/2371264 . JSTOR 2371264 . 
• Sobottka, M. (2022). "Algunas notas sobre la clasificación de espacios de desplazamiento: desplazamientos de tipo finito; desplazamientos sóficos; y desplazamientos definidos finitamente". Boletín de la Sociedad Matemática Brasileña . Nueva serie. 53 (3): 981– 1031. arXiv : 2010.10595 . doi : 10.1007/s00574-022-00292-x . S2CID 254048586 .