Espacio de cambio

Conjunto de infinitas palabras.

En dinámica simbólica y ramas relacionadas de las matemáticas , un espacio de desplazamiento o subdesplazamiento es un conjunto de infinitas palabras que representan la evolución de un sistema discreto . De hecho, los espacios de turno y los sistemas dinámicos simbólicos a menudo se consideran sinónimos . Los espacios de turnos más estudiados son los subcambios de tipo finito y los turnos sóficos.

En el marco clásico ^[1] un espacio de desplazamiento es cualquier subconjunto de , donde es un conjunto finito, 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 de traducción 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 . Denotemos la identidad de . Considere un conjunto no vacío (un alfabeto) con topología discreta y defínalo como el conjunto de todos los patrones sobreindexados por . Para y un subconjunto , denotamos la restricción de a los índices de as . ${\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 constituye un espacio topológico de Hausdorff totalmente desconectado. En el caso de ser finito, se deduce que es compacto. Sin embargo, si no es finito, 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 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 , y para cada uno , deja . 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 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 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 cerrado bajo la topología de e invariante bajo traducciones, es decir, para todos . ^{[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 uno , defina y . Una forma equivalente de definir un espacio de turno es tomar un conjunto de patrones prohibidos y definir un espacio de turno 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 turno.

Dado un espacio de desplazamiento y un conjunto finito de índices , sea donde, representa la palabra vacía, y 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\}.}$

Tenga en cuenta que, dado que es un espacio de desplazamiento, if es una traducción de , es decir, para algunos , entonces si y sólo si existe tal que if . En otras palabras, y contienen la misma configuración de traducción de módulo. 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 idioma de . En el contexto general aquí planteado, el lenguaje de un espacio de turno no tiene el mismo significado que en la Teoría del Lenguaje Formal , sino en el marco clásico que considera que el alfabeto es finito, y siendo o con la adición habitual, el lenguaje de un turno. El espacio 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 números enteros no negativos ( ) con la suma habitual, o el conjunto de todos los números enteros ( ) con la suma habitual. En ambos casos, el elemento identidad corresponde al número 0. Además, cuando , dado que todo puede generarse a partir del número 1, es suficiente considerar un mapa de desplazamiento único dado por para todos . Por otro lado, para el caso de , dado que todo puede generarse a partir de los números {-1, 1}, es suficiente considerar dos mapas de desplazamiento dados 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 suma habitual (independientemente de la cardinalidad de ), debido a su estructura algebraica, basta considerar sólo cilindros de 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 turno vendrá 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 se indicó anteriormente, sin especificar el índice de dónde están prohibidas las palabras, entonces simplemente capturaremos espacios de desplazamiento que son 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 habitual, se deduce que es finito si y sólo si es finito, lo que lleva a la definición clásica de un desplazamiento de tipo finito como aquellos espacios de desplazamiento tales que para algunos finitos . ${\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 varios tipos de espacios de turnos, los más estudiados son los turnos de tipo finito y los turnos 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 tal que , y es un desplazamiento sófico si es la imagen de un desplazamiento de tipo finito bajo un bloque deslizante. código ^[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 sólo 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 "sofic" fue acuñado por Weiss (1973), basándose 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 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 como las condiciones adicionales de los códigos de bloques deslizantes se satisfacen trivialmente siempre que sean finitos. ${\displaystyle \Lambda =X_{F}}$ ${\displaystyle M_{F}}$ ${\displaystyle A}$

Sistemas dinámicos topológicos en espacios de turno.

Los espacios de cambio son los espacios topológicos en los que normalmente 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 están topológicamente conjugados (o simplemente conjugados) si para cada mapa de desplazamiento se deduce que los sistemas dinámicos topológicos y están topológicamente conjugados , es decir, si existe un mapa continuo tal que . Estos mapas se conocen como códigos de bloques deslizantes generalizados o simplemente como códigos de bloques deslizantes siempre que sean uniformemente continuos. ^[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 mapa continuo desde hacia sí mismo definirá un sistema dinámico topológico , en dinámica simbólica es habitual considerar sólo mapas continuos que conmutan con mapas de todos los desplazamientos, es decir, mapas que son códigos de bloques deslizantes 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} }}$

Dejar . 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 prima no es sófico (esto se puede demostrar usando el lema de bombeo ). ${\displaystyle A=\{a,b\}}$

El espacio de infinitas cadenas 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 mapa de Baker , o más bien es homomórfico al mapa de Baker. ${\displaystyle \{0,1\}^{\mathbb {Z} }}$

Ver también

• Mapa de la tienda
• mapa de desplazamiento de bits
• código gris

Notas a pie de página

1. Es común referirse a un espacio de desplazamiento utilizando únicamente la expresión desplazamiento o subdesplazamiento . Sin embargo, algunos autores utilizan los términos desplazamiento y subdesplazamiento para conjuntos de pares infinitos que son simplemente invariantes bajo los mapas de desplazamiento, 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.; Marco, Brian (1995). Una introducción a la dinámica simbólica y la codificación . Cambridge: prensa de la Universidad de Cambridge. ISBN 978-0-521-55900-3.
2. Ceccherini-Silberstein, T.; Coornaert, M. (2010). Autómatas celulares y grupos Springer Monographs in Mathematics. Monografías de Springer en Matemáticas. 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 turnos: turnos de tipo finito; turnos soficos; y turnos finitamente definidos". Boletín de la Sociedad Brasileña de Matemáticas . Series nuevas. 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 sistemas soficos y de tipo finito", Monatsh. Matemáticas. , 77 (5): 462–474, doi :10.1007/bf01295322, SEÑOR  0340556, S2CID  123440583. Weiss no describe el origen de la palabra más que llamarla neologismo; sin embargo, su origen hebreo lo afirma el crítico de MathSciNet, RL Adler.

Otras lecturas

• Ceccherini-Silberstein, T.; Coornaert, M. (2010). Autómatas celulares y grupos Monografías de Springer en Matemáticas . Springer Verlag. ISBN 978-3-642-14034-1.
• Lind, Douglas; Marco, Brian (1995). Una introducción a la dinámica simbólica y la codificación . Cambridge Reino Unido: Cambridge University Press. ISBN 0-521-55900-6.
• Lotario, M. (2002). "Palabras finitas e infinitas". Combinatoria algebraica de 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 turnos: turnos de tipo finito; turnos soficos; y turnos finitamente definidos". Boletín de la Sociedad Brasileña de Matemáticas . Series nuevas. 53 (3): 981–1031. arXiv : 2010.10595 . doi :10.1007/s00574-022-00292-x. S2CID  254048586.