12.1: Tamaños de espacio de regla y espacio de fase

Última actualización
Guardar como PDF

Page ID: 115721

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Una de las características únicas de los modelos de CA típicos es que el tiempo, el espacio y los estados de las celdas son todos discretos. Debido a tal discreción, el número de todas las posibles funciones de transición de estado es finito, es decir, solo hay un número finito de “universos” posibles en un entorno de CA dado. Además, si el espacio es finito, también son enumerables todas las configuraciones posibles de todo el sistema. Esto significa que, para configuraciones de CA razonablemente pequeñas, se puede realizar una búsqueda exhaustiva de todo el espacio de reglas o espacio de fases para estudiar las propiedades de todos los “universos paralelos”. Stephen Wolfram realizó una búsqueda tan exhaustiva de un espacio binario de reglas de CA para ilustrar la posible dinámica de CA [34, 46].

Calculemos qué tan grande puede ser un espacio de reglas/espacio de fase de una configuración de CA dada. Aquí asumimos lo siguiente:

Dimensión del espacio:\(D\)
Longitud del espacio en cada dimensión:\(L\)
Radio de barrio:\(R\)
Número de estados para cada celda:\(K\)

Para calcular el número de reglas posibles, primero necesitamos conocer el tamaño del vecindario de cada celda. Para cada dimensión, la longitud de cada lado de un vecindario viene dada por\(2r + 1\), incluyendo la propia celda. En un espacio\(D\) -dimensional, esto se eleva al poder de\(D\), asumiendo que el vecindario es un cubo\(D\) -dimensional (hiper). Entonces, el tamaño (volumen) del barrio viene dado por

\[n=(2r+1)^{D}\label{(12.1)} \]

Cada una de las\(n\) celdas de un barrio puede tomar uno de\(k\) los estados. Por lo tanto, el número total de situaciones locales posibles viene dado por

\[m=k^{n}=k^{2r+1^{D}}\label{(12.2)} \]

Ahora podemos calcular el número de todas las posibles funciones de transición de estado. Una función tiene que mapear cada una de las m situaciones a uno de los\(k\) estados. Por lo tanto, el número de mapeos posibles viene dado por

\[R =k^{m}= k^{k^{n}}=k^{k^{(2r+1)^{D}}}. \label{(12.3)} \]

Por ejemplo, un modelo de\((k = 2)\) CA\((D = 1)\) binaria unidimensional con radio 1\((r = 1)\) tiene\(2^{(2×1+1)^{1}} = 2^{3} = 8\) diferentes situaciones posibles, y así hay funciones de\(2^{8} = 256\) transición de estado posibles en este universo CA ¹. Esto parece razonable, pero ten cuidado— este número explota rápidamente a escalas astronómicas para mayores\(k\),\(r\), o\(D\).

Ejercicio\(\PageIndex{1}\):

Calcular el número de posibles funciones de transición de estado para un modelo de CA bidimensional con dos estados y vecindarios de Moore (i.e.,\(r = 1\)).

Ejercicio\(\PageIndex{2}\):

Calcular el número de posibles funciones de transición de estado para un modelo tridimensional de CA con tres estados y vecindarios 3-D Moore (i.e.,\(r = 1\)).

Debió haber enfrentado algunos números violentamente grandes en estos ejercicios. Varias suposiciones de simetría (por ejemplo, simetrías rotacionales, simetrías refleccionales, reglas totalistas, etc.) a menudo se adoptan para reducir el tamaño de los espacios de reglas de los modelos de CA.

¿Qué tal el tamaño del espacio de fase? En realidad, puede ser mucho más manejable en comparación con el tamaño de los espacios de reglas, dependiendo de qué tan grande\(L\) sea. El número total de celdas en el espacio (es decir, el volumen del espacio) viene dado por
\[V=L^{D}.\label{(12.4)} \]

Cada celda en este volumen toma uno de los\(k\) estados, por lo que el número total de configuraciones posibles (es decir, el tamaño del espacio de fase) viene dado simplemente por

\[S=k^{V} =k^{L^{D}}. \label{(12.5)} \]

Por ejemplo, un modelo de CA binaria unidimensional con\(L = 10\) configuraciones\(2^{10^{1}} = 1024\) posibles, un modelo de CA binario bidimensional con\(L = 10\) configuraciones\((2^{10^{2}} ≈ 1.27 × 10^{30}\) posibles. Este último es grande, pero no es tan grande en comparación con el tamaño de los espacios de reglas que viste en los ejercicios anteriores.

Ejercicio\(\PageIndex{3}\):

Calcular el número de todas las configuraciones posibles de un modelo de CA bidimensional y de tres estados con\(L = 100\).

¹ Existe un conocido esquema de numeración de reglas para este entorno en particular propuesto por Wolfram, pero no lo discutimos en detalle en este libro de texto.