Cambiar espacio

Conjunto de palabras infinitas

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 de , donde 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 , donde es cualquier conjunto no vacío y es cualquier monoide . ^{[2] [3]} ${\displaystyle \Lambda }$ ${\displaystyle A^{\mathbb {Z} }:=\{(x_{i})_{i\in \mathbb {Z} }:\ x_{i}\in A\ \forall i\in \mathbb {Z} \}}$ ${\displaystyle A}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$

Definición

Sea un monoide , y dado , denotemos la operación de con por el producto . Sea denotemos la identidad de . Considérese un conjunto no vacío (un alfabeto) con la topología discreta, y definamos como el conjunto de todos los patrones sobre indexados por . Para y un subconjunto , denotamos la restricción de a los índices de como . ${\displaystyle \mathbb {G} }$ ${\displaystyle g,h\in \mathbb {G} }$ ${\displaystyle g}$ ${\displaystyle h}$ ${\displaystyle gh}$ ${\displaystyle \mathbf {1} _{\mathbb {G} }}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle A}$ ${\displaystyle A^{\mathbb {G} }}$ ${\displaystyle A}$ ${\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}}$

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

Esta topología será metrizable si y sólo si es numerable, 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 , y para cada , sea . El cilindro dado por y es el conjunto ${\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\}.}$

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

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

Dado , el mapa de desplazamiento g en se denota por y se define como ${\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} }}$.

Un espacio de desplazamiento sobre el alfabeto es un conjunto que está cerrado bajo la topología de e invariante bajo traslaciones, es decir, para todo . ^{[nota 1]} Consideramos en el espacio de desplazamiento la topología inducida de , que tiene como conjuntos abiertos básicos los cilindros . ${\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 }$

Para cada , defina , y . Una forma equivalente de definir un espacio de desplazamiento es tomar un conjunto de patrones prohibidos y definir un espacio de desplazamiento como el conjunto ${\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\}.}$

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

Lenguaje del espacio de desplazamiento

Dado un espacio de desplazamiento y un conjunto finito de índices , sea , donde representa la palabra vacía, y para sea el conjunto de todas las configuraciones finitas de que aparecen en alguna secuencia de , es decir, ${\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\}.}$

Nótese que, puesto que es un espacio de desplazamiento, si es una traslación de , es decir, para algún , entonces si y sólo si existe tal que si . En otras palabras, y contienen las mismas configuraciones módulo traslación. Llamaremos al conjunto ${\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 )}$

el lenguaje de . En el contexto general aquí establecido, el lenguaje de un espacio de desplazamiento no tiene el mismo significado que en la teoría del lenguaje formal , pero en el marco clásico que considera que el alfabeto es finito y que es o con la adición habitual, el lenguaje de un espacio de desplazamiento es un lenguaje formal. ${\displaystyle \Lambda }$ ${\displaystyle A}$ ${\displaystyle \mathbb {G} }$ ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$

Marco clásico

El marco clásico para los espacios de desplazamiento consiste en considerar el alfabeto como finito, y como el conjunto de los enteros no negativos ( ) con la adición usual, o el conjunto de todos los enteros ( ) con la adición usual. En ambos casos, el elemento identidad corresponde al número 0. Además, cuando , ya que todos pueden generarse a partir del número 1, es suficiente considerar una única función de desplazamiento dada por para todos . Por otro lado, para el caso de , ya que todos pueden generarse a partir de los números {-1, 1}, es suficiente considerar dos funciones de desplazamiento dadas para todos por y por . ${\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}}$

Además, siempre que sea o con la adición habitual (independientemente de la cardinalidad de ), debido a su estructura algebraica, es suficiente considerar solo cilindros en la forma ${\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\}.}$

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

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

donde y representa la palabra vacía, y ${\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\}.}$

De la misma manera, para el caso particular de , se deduce que para definir un espacio de desplazamiento no necesitamos especificar el índice de en el que se definen las palabras prohibidas de , es decir, podemos simplemente considerar y luego ${\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\}.}$

Sin embargo, si definimos un espacio de desplazamiento como el anterior, sin especificar el índice de donde las palabras están prohibidas, entonces solo capturaremos espacios de desplazamiento que sean invariantes a través del mapa de desplazamiento, es decir, tales que . De hecho, para definir un espacio de desplazamiento tal que será necesario especificar a partir de qué índice están prohibidas las palabras de . ${\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}$

En particular, en el marco clásico de ser finito, y ser ) o con la adición usual, se sigue que es finito si y sólo si es finito, lo que conduce a la definición clásica de un desplazamiento de tipo finito como aquellos espacios de desplazamiento tales que para algún finito . ${\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}$

Algunos tipos de espacios de turno

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 en que el alfabeto sea finito, un espacio de desplazamiento es un desplazamiento de tipo finito si podemos tomar un conjunto finito de patrones prohibidos tales que , y es un desplazamiento sófico si es la imagen de un desplazamiento de tipo finito bajo el código de bloque deslizante ^[1] (es decir, un mapa que es continuo e invariante para todos los mapas de desplazamiento ). Si es finito y es o con la adición habitual, entonces el desplazamiento es un desplazamiento sófico si y solo si es un lenguaje regular . ${\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 )}$

El nombre "sófico" 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 es infinito, es posible definir desplazamientos de tipo finito como espacios de desplazamiento para aquellos en los que se puede tomar un conjunto de palabras prohibidas tales que ${\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\},}$

es finito y . ^[3] En este contexto de alfabeto infinito, un cambio sófico se definirá como la imagen de un cambio de tipo finito bajo una clase particular de códigos de bloque deslizante. ^[3] Tanto la finitud de como las condiciones adicionales de los códigos de bloque deslizante se satisfacen trivialmente siempre que sea finito. ${\displaystyle \Lambda =X_{F}}$ ${\displaystyle M_{F}}$ ${\displaystyle A}$

Sistemas dinámicos topológicos en espacios de desplazamiento

Los espacios de desplazamiento son los espacios topológicos en los que habitualmente se definen los sistemas dinámicos simbólicos .

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

Se dice que dos espacios de desplazamiento y son topológicamente conjugados (o simplemente conjugados) si para cada función de desplazamiento se sigue que los sistemas dinámicos topológicos y son topológicamente conjugados , es decir, si existe una función continua tal que . Dichas funciones se conocen como códigos de bloque deslizante generalizados o simplemente como códigos de bloque deslizante siempre que sea uniformemente continua. ^[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 }$

Aunque cualquier función continua de a sí misma definirá un sistema dinámico topológico , en dinámica simbólica es habitual considerar únicamente funciones continuas que conmutan con funciones de desplazamiento total, es decir, funciones que son códigos de bloque deslizante generalizados. El sistema dinámico se conoce como " autómata celular generalizado" (o simplemente como autómata celular siempre que sea uniformemente continuo). ${\displaystyle \Phi }$ ${\displaystyle \Lambda \subset A^{\mathbb {G} }}$ ${\displaystyle (\Lambda ,\Phi )}$ ${\displaystyle \Phi :\Lambda \to \Lambda }$ ${\displaystyle g}$ ${\displaystyle (\Lambda ,\Phi )}$ ${\displaystyle \Phi }$

Ejemplos

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

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

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

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

Véase también

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

Notas al pie

1. Es común referirse a un espacio de desplazamiento utilizando simplemente la expresión shift o subshift . Sin embargo, algunos autores utilizan los términos shift y subshift para conjuntos de patrones infinitos que son simplemente invariantes bajo los mapas -shift, y reservan el término espacio de desplazamiento para aquellos que también están cerrados para la topología prodiscreta. ${\displaystyle g}$

Referencias

1. Lind, Douglas A.; Marcus, Brian (1995). Introducción a la dinámica simbólica y la codificación . Cambridge: Cambridge University Press. ISBN 978-0-521-55900-3.
2. Ceccherini-Silberstein, T.; Coornaert, M. (2010). Autómatas celulares y grupos Springer Monographs in Mathematics. Springer Monographs in Mathematics. Springer Verlag. doi :10.1007/978-3-642-14034-1. ISBN 978-3-642-14033-4.
3. Sobottka, Marcelo (septiembre de 2022). "Algunas notas sobre la clasificación de espacios de desplazamientos: desplazamientos de tipo finito; desplazamientos sóficos; y desplazamientos finitamente definidos". Boletín de la Sociedad Brasileña de Matemática . Nuevas Series. 53 (3): 981–1031. arXiv : 2010.10595 . doi :10.1007/s00574-022-00292-x. ISSN  1678-7544. S2CID  254048586.
4. Weiss, Benjamin (1973), "Subdesplazamientos de tipos finitos y sistemas sóficos", Monatsh. Math. , 77 (5): 462–474, doi :10.1007/bf01295322, MR  0340556, S2CID  123440583Weiss no describe el origen de la palabra más allá de llamarla un neologismo; sin embargo, su origen hebreo es afirmado por el revisor de MathSciNet, RL Adler.

Lectura adicional

• 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". Revista estadounidense de matemáticas . 60 (4): 815–866. doi :10.2307/2371264. JSTOR  2371264.
• Sobottka, M. (2022). "Algunas notas sobre la clasificación de espacios de desplazamientos: desplazamientos de tipo finito; desplazamientos sóficos; y desplazamientos finitamente definidos". Boletín de la Sociedad Brasileña de Matemática . Nuevas Series. 53 (3): 981–1031. arXiv : 2010.10595 . doi :10.1007/s00574-022-00292-x. S2CID  254048586.