¿Números irracionales generados por un autómata celular determinista?

Question

¿Números irracionales generados por un autómata celular determinista?

Matemáticas
autómata celular
Numeros irracionales

yuriy s

Si consideramos un autómata celular 1D simple (que actúa sobre una cadena binaria) y registramos un valor en una posición fija en la cadena, podemos interpretar la secuencia registrada como un número binario.

La mayoría de los autómatas celulares deterministas simples generan secuencias periódicas de dígitos binarios que pueden interpretarse como números racionales.

Sin embargo, existen CA deterministas 'aleatorias', como la regla 30 de CA elemental, descubierta por S. Wolfram. A partir de un único punto, genera datos que son lo suficientemente aleatorios como para usarse como generador de números aleatorios. Consulte este documento para obtener más información.

Ahora, dado que esta CA tiene reglas perfectamente deterministas (y simples), ¿qué podemos decir sobre los números que genera en posiciones de cadena fijas?

Dado que la mayor parte de la "aleatoriedad" ocurre en el lado derecho, veamos los números que obtenemos en las posiciones desde el centro hacia la derecha, comenzando desde la parte superior. $1$ en cada caso (ver la figura). Se considera que todos los números tienen partes enteras cero y se convierten a la notación decimal de binario:

a_{0} = 0.8623897839473840486408002460867511281 \dots

$a_0=0.8623897839473840486408002460867511281\dots$

a_{1} = 0.6619938131535679545367590611375473724 \dots

$a_1=0.6619938131535679545367590611375473724\dots$

a_{2} = 0.7759963493462055882598583123808285092 \dots

$a_2=0.7759963493462055882598583123808285092\dots$

a_{3} = 0.7313593429560050953478343145780694591 \dots

$a_3=0.7313593429560050953478343145780694591\dots$

a_{4} = 0.8215879687059052475349289186091204860 \dots

$a_4=0.8215879687059052475349289186091204860\dots$

a_{5} = 0.6314259431664999548181068438831291123 \dots

$a_5=0.6314259431664999548181068438831291123\dots$

a_{6} = 0.8079966728503828647993510584534608703 \dots

$a_6=0.8079966728503828647993510584534608703\dots$

¿Podemos probar/refutar que estos números son irracionales? trascendental? ¿O solo podemos adivinar basándonos en experimentos directos? ¿Qué pasa con otros autómatas celulares "aleatorios" de este tipo?

N74

A menos que no tenga dígitos infinitos, su número es racional. Y solo puedes tener infinitos dígitos en un tiempo infinito.

usuario2469

@ N74 Sí, pero los autómatas celulares como este continúan para siempre. El OP acaba de mostrar los primeros pasos. Con cada nuevo paso, obtienes más dígitos.

yuriy s

@ N74, ¿estás diciendo que los números irracionales no existen? Nadie fue capaz de obtener infinitos dígitos de

π

$\pi$ todavía

N74

@YuriyS Estoy diciendo que ningún proceso determinista puede generar un número irracional, a menos que se ejecute para siempre. Piensa en el ejemplo clásico de la construcción de un número irracional:

a_{0} = 0.1

$a_0=0.1$ ,

a_{1} = 0.101

$a_1=0.101$ ,

a_{2} = 0.101001

$a_2=0.101001$ ,

a_{3} = 0.1010010001

$a_3=0.1010010001$ ;

a_{\infty}

$a_{\infty}$ es trascendental pero todo

a_{n}

$a_n$ son racionales.

N74

@barrycarter Los números irracionales deben tener una infinidad contable de dígitos, deje que se ejecute el algoritmo y, al final del universo, tendrá un número irracional. Ningún número representable por máquina es irracional.

yuriy s

@N74, de nuevo, ¿estás diciendo eso?

π

$\pi$ ,

e

$e$ ,

\sqrt{2}

$\sqrt{2}$ , etc, no existen? ¿Por qué una secuencia de Cauchy no puede ser definida por un autómata celular (u otra máquina)?

N74

@YuriyS por tiempo y recursos: ninguna máquina tiene limitaciones en ambos.

yuriy s

@ N74, lo siento, ¿podría aclarar su posición sobre los números irracionales en general? ¿Existen aunque no podamos calcularlos en un tiempo finito?

N74

@YuriyS Seguro que los irracionales existen y tenemos mucha evidencia de esto en nuestro mundo continuo. El problema es generarlos en una máquina ... sin memoria infinita, está obligado a repetir la secuencia, primero o último.

usuario2469

Para resolver esto, ¿podemos decir que tenemos una secuencia de números racionales computables cuyo límite converge a un número irracional?

jim jim

el punto es este, ningún autómata finito determinista puede generar números irracionales.

yuriy s

@Arjang, ¿entonces no hay forma de generar números irracionales?

jim jim

@YuriyS: claro que lo hay, tome por ejemplo que los dígitos binarios sean 0.10110011100011110000 ... ese es un número irracional, tal vez incluso trascendental. los dígitos son fáciles de generar, siempre que no se repitan desde algunos puntos en adelante.

jim jim

@YuriyS: acabo de inventar ese número, puedes obtener más información sobre números como ese en este enlace mathworld.wolfram.com/LiouvillesConstant.html

yuriy s

@Arjang, pero ese es un proceso determinista, ¿no? Y por cierto, ¿qué quieres decir con 'autómata finito'? Cualquier proceso que nosotros (como humanidad) hayamos hecho alguna vez es finito

jim jim

@YuriyS: el proceso determinista no es lo mismo que la máquina de estado finito determinista, y sí, no solo lo que dijiste es cierto, también el universo entero no es suficiente para representar todos los dígitos de la raíz cuadrada de dos. es posible que también desee ver los límites de cálculo, el número omega y las órdenes de infinito.

yuriy s

@Arjang, podemos probar que

\sqrt{2}, e, π

$\sqrt{2}, e, \pi$ son irracionales, a pesar del hecho de que cualquier expansión decimal de ellos que hayamos creado es una aproximación racional. Los números sobre los que pregunto deben tomarse como un límite que va al infinito, suponiendo que sigamos generando la CA

jim jim

@YuriyS: Lo siento, tal vez me estoy perdiendo algo aquí. Cualquier número con dígitos aleatorios es irracional seguro. Volveré a leer la pregunta para entender la pregunta.

jim jim

No estoy seguro de lo que está preguntando, pero filosóficamente los números naturales no existen en nuestro universo, sus representaciones sí.

yuriy s

@Arjang, ahora que lo pienso, mi pregunta es más '¿qué consideramos aleatorio'? Vea el documento que vinculé, tal vez entienda lo que estoy preguntando

Zach466920

@ N74 "Sin duda, los irracionales existen y tenemos muchas pruebas de esto en nuestro mundo continuo. El problema es generarlos en una máquina ... sin memoria infinita, está obligado a repetir la secuencia, primero o último". Déjame recordarte que esto es matemática. Lo que dijiste se refiere a la viabilidad en la realidad. Sin embargo, ambos sabemos cuán confiable es la factibilidad de un indicador para predecir la posibilidad.

Zach466920

Necesito una aclaración sobre cómo estás obteniendo el

a_{n}

$a_n$ . por ejemplo para

a_{0}

$a_0$ parece que comienza desde la parte superior en el centro y luego crea un número binario usando los autómatas celluar para los valores. Cada valor en el centro es

0

$0$ o

1

$1$ . Por ejemplo, la primera fila tiene

1

$1$ , entonces el segundo tiene

1

$1$ el tercero tiene

0

$0$ ¿etcétera?

yuriy s

@ Zach466920, cada número se crea tomando valores de celda en una columna vertical como 0 o 1.

a_{0}

$a_0$ es una columna central. Pareces entender correctamente. Si estuviera tomando filas, cada número tendría una expansión finita, es decir, sería racional

Respuestas (2)

¿Números irracionales generados por un autómata celular determinista?

A menos que no tenga dígitos infinitos, su número es racional. Y solo puedes tener infinitos dígitos en un tiempo infinito.
@ N74 Sí, pero los autómatas celulares como este continúan para siempre. El OP acaba de mostrar los primeros pasos. Con cada nuevo paso, obtienes más dígitos.
@ N74, ¿estás diciendo que los números irracionales no existen? Nadie fue capaz de obtener infinitos dígitos de $\pi$ todavía
@YuriyS Estoy diciendo que ningún proceso determinista puede generar un número irracional, a menos que se ejecute para siempre. Piensa en el ejemplo clásico de la construcción de un número irracional: $a_0=0.1$ , $a_1=0.101$ , $a_2=0.101001$ , $a_3=0.1010010001$ ; $a_{\infty}$ es trascendental pero todo $a_n$ son racionales.
@barrycarter Los números irracionales deben tener una infinidad contable de dígitos, deje que se ejecute el algoritmo y, al final del universo, tendrá un número irracional. Ningún número representable por máquina es irracional.
@N74, de nuevo, ¿estás diciendo eso? $\pi$ , $e$ , $\sqrt{2}$ , etc, no existen? ¿Por qué una secuencia de Cauchy no puede ser definida por un autómata celular (u otra máquina)?
@YuriyS por tiempo y recursos: ninguna máquina tiene limitaciones en ambos.
@ N74, lo siento, ¿podría aclarar su posición sobre los números irracionales en general? ¿Existen aunque no podamos calcularlos en un tiempo finito?
@YuriyS Seguro que los irracionales existen y tenemos mucha evidencia de esto en nuestro mundo continuo. El problema es generarlos en una máquina ... sin memoria infinita, está obligado a repetir la secuencia, primero o último.
Para resolver esto, ¿podemos decir que tenemos una secuencia de números racionales computables cuyo límite converge a un número irracional?
el punto es este, ningún autómata finito determinista puede generar números irracionales.
@Arjang, ¿entonces no hay forma de generar números irracionales?
@YuriyS: claro que lo hay, tome por ejemplo que los dígitos binarios sean 0.10110011100011110000 ... ese es un número irracional, tal vez incluso trascendental. los dígitos son fáciles de generar, siempre que no se repitan desde algunos puntos en adelante.
@YuriyS: acabo de inventar ese número, puedes obtener más información sobre números como ese en este enlace mathworld.wolfram.com/LiouvillesConstant.html
@Arjang, pero ese es un proceso determinista, ¿no? Y por cierto, ¿qué quieres decir con 'autómata finito'? Cualquier proceso que nosotros (como humanidad) hayamos hecho alguna vez es finito
@YuriyS: el proceso determinista no es lo mismo que la máquina de estado finito determinista, y sí, no solo lo que dijiste es cierto, también el universo entero no es suficiente para representar todos los dígitos de la raíz cuadrada de dos. es posible que también desee ver los límites de cálculo, el número omega y las órdenes de infinito.
@Arjang, podemos probar que $\sqrt{2}, e, \pi$ son irracionales, a pesar del hecho de que cualquier expansión decimal de ellos que hayamos creado es una aproximación racional. Los números sobre los que pregunto deben tomarse como un límite que va al infinito, suponiendo que sigamos generando la CA
@YuriyS: Lo siento, tal vez me estoy perdiendo algo aquí. Cualquier número con dígitos aleatorios es irracional seguro. Volveré a leer la pregunta para entender la pregunta.
No estoy seguro de lo que está preguntando, pero filosóficamente los números naturales no existen en nuestro universo, sus representaciones sí.
@Arjang, ahora que lo pienso, mi pregunta es más '¿qué consideramos aleatorio'? Vea el documento que vinculé, tal vez entienda lo que estoy preguntando
@ N74 "Sin duda, los irracionales existen y tenemos muchas pruebas de esto en nuestro mundo continuo. El problema es generarlos en una máquina ... sin memoria infinita, está obligado a repetir la secuencia, primero o último". Déjame recordarte que esto es matemática. Lo que dijiste se refiere a la viabilidad en la realidad. Sin embargo, ambos sabemos cuán confiable es la factibilidad de un indicador para predecir la posibilidad.
Necesito una aclaración sobre cómo estás obteniendo el $a_n$ . por ejemplo para $a_0$ parece que comienza desde la parte superior en el centro y luego crea un número binario usando los autómatas celluar para los valores. Cada valor en el centro es $0$ o $1$ . Por ejemplo, la primera fila tiene $1$ , entonces el segundo tiene $1$ el tercero tiene $0$ ¿etcétera?
@ Zach466920, cada número se crea tomando valores de celda en una columna vertical como 0 o 1. $a_0$ es una columna central. Pareces entender correctamente. Si estuviera tomando filas, cada número tendría una expansión finita, es decir, sería racional

Zach466920 · Answer 1

La respuesta en sí no es muy sorprendente o esclarecedora, así que lo siento: /

En primer lugar, dado que publicó una imagen de la regla 30, discutida aquí , consideraremos la generación de números solo a partir de esa CA.

Segundo, recuerda la definición de un número irracional ,

Un número irracional es un número que no se puede expresar como una fracción p/q para ningún número entero p y q.

Corolario 1:

Los números irracionales tienen expansiones decimales que ni terminan ni se vuelven periódicas.

Prueba: Suponga que la expansión decimal se repite. Entonces el número es, por definición, racional . Por lo tanto, nuestra suposición es falsa y el corolario es verdadero.

Ahora ha sido probado por Jen 1990 que con el estado inicial de una sola celda negra, la secuencia de colores obtenida en dos celdas adyacentes no es periódica. Corroborado por Gray 2003 .

Entonces, si definimos una secuencia de números usando los estados de celda generados por la regla 30, entonces los dígitos no serán periódicos. Por el Corolario 1, si los dígitos no son periódicos, entonces el número es irracional.

Así que veamos tu(s) pregunta(s)

¿Podemos probar/refutar que estos números son irracionales?

Podemos probar que estos números son irracionales, por la regla 30.

trascendental?

Casi seguro.

¿Qué pasa con otros autómatas celulares "aleatorios" de este tipo?

Cualquier autómata celular con evolución no periódica también generará números irracionales.

Cuando dices "casi seguro", entiendo que significa que sería muy sorprendente si alguno fuera algebraico.
@ user254665 En realidad, lo digo en sentido matemático. Dado que la regla 30 también es caótica, las celdas evolucionan de forma pseudoaleatoria. Casi seguro, tal número es trascendental.
Pequeño punto: para la Regla 30, aunque es muy poco probable, sigue siendo una pregunta abierta si cada columna infinita nunca cae o no en un ciclo; se ha demostrado que como máximo una columna puede hacer esto. Si de alguna manera hubiera una columna repetida (absolutamente no la hay, pero nadie puede probarlo), esa columna sería racional.

Gro-Tsen · Answer 2

Si bien casi todos los números reales son trascendentales, es endiabladamente difícil probarlo para números reales específicos, especialmente aquellos dados por su base. $b$ expansión. (Para aquellas cantidades "naturales" para las que se conoce una prueba de trascendencia, generalmente se trata de ver estas cantidades como valores particulares de funciones especiales y usar técnicas de análisis de tales funciones). A diferencia de la irracionalidad (un número es irracional si su base $b$ la expansión no es eventualmente periódica), no hay nada análogo para la trascendencia.

Incluso para la constante de Champernowne de aspecto muy simple ( $0.12345678910111213...$ ), era difícil probar su trascendencia . No debe esperar una prueba de trascendencia de cantidades cuya base $b$ las expansiones están definidas por autómatas celulares.

Sin embargo, hay un resultado notable que se parece al menos a lo que está preguntando, al menos en el sentido de que las palabras clave "autómata", "base $b$ expansión" y "trascendencia" aparecen en él:

Si $x$ es un número real (y $b\geq 2$ entero) tal que la base $b$ Expansión de $x$ no es eventualmente periódico, y " $b$ -automático" en el sentido de que el $i$ -ésimo decimal de $x$ en base $b$ puede ser calculado por un autómata finito a partir de la base $b$ Expansión de $i$ mismo, entonces $x$ es trascendental.

Una primera "prueba" apareció como: Loxton & van der Poorten, " Propiedades aritméticas de los autómatas: secuencias regulares ", J. Reine Angew. Matemáticas. 392 (1988), 57–69; sin embargo, ese documento contiene un defecto. Una prueba correcta, junto con resultados relacionados y conjeturas, apareció mucho más recientemente: Adamczewski & Bugeaud, “ On the complex of algebraic numbers I. Expansions in integer bases ”, Ann. de Matemáticas. 165 (2007), 547–565. ( Aquí hay una encuesta relacionada con tales preguntas, aunque no parece ser consciente de que el artículo de Loxton & van der Poorten tiene fallas).

Este resultado implica, por ejemplo, que el número cuya expansión binaria es la secuencia de Morse-Thue , a saber, $0.01101001100101101001...$ , es trascendental (porque ciertamente es automático y no periódico). Esto es ciertamente lo más cerca que estará del tipo de cantidades que estaba preguntando.

(También es notable que, para las series de potencias formales sobre campos finitos, existe un resultado debido a Christol, Kamae, Mendès-France y Rauzy que dice esencialmente lo "opuesto" del citado anteriormente: los coeficientes de las series de potencias formales son automáticos si y solo si la serie de potencias es algebraica .)

No estoy seguro de por qué es tan pesimista acerca de probar que un número generado por autómatas celulares es trascendental, cuando inmediatamente cita un resultado muy similar (y maravilloso) sobre cómo los números finitos generados por autómatas son trascendentales .
@JackM Porque la teoría de los autómatas finitos es extremadamente restringida y bien entendida, e incluso entonces resultó ser inmensamente difícil probar la trascendencia de las expansiones que reconocen; los autómatas celulares pueden hacer casi cualquier cosa, creo que no es razonable esperar resultados de trascendencia allí (pero, por supuesto, ¡me encantaría que me demuestren que estoy equivocado!).
@Gro-Tsen, muchas gracias por tu respuesta. Lo siento, no pude recompensarte, pero la otra respuesta me parece más relevante.
@Gro-Tsen Creo que hay dos preguntas distintas aquí: 'dada una CA, ¿podemos probar que alguno de los números que genera es trascendental?' y '¿Podemos exhibir una CA que genere números trascendentales de esa manera?' Es probable que la respuesta a la primera sea tan difícil como usted dice, pero creo que la respuesta a la segunda debería ser positiva traduciéndola sobre una construcción apropiada.

¿Números irracionales generados por un autómata celular determinista?

yuriy s

N74

usuario2469

yuriy s

N74

N74

yuriy s

N74

yuriy s

N74

usuario2469

jim jim

yuriy s

jim jim

jim jim

yuriy s

jim jim

yuriy s

jim jim

jim jim

yuriy s

Zach466920

Zach466920

yuriy s

Respuestas (2)

Zach466920

DanielWainfleet

Zach466920

Trevor

Gro-Tsen

gato m

Gro-Tsen

yuriy s

Steven Stadnicki