Autómatas celulares en la conjetura de Collatz

Tengo un Autómata Celular que de cualquier entero inicial (condición inicial del autómata) genera estados de secuencias de Collatz. La vecindad del autómata tiene la forma de un L-tetromino (que incluye dos estados de tiempo). El fondo (quiescente) se representa como 0 (el estado cero). El otro 1 -state (on-state) genera borde activo en el lado izquierdo durante la generación del autómata. El borde es la parte interesante porque ahí es donde la generación "actual" aumenta (es impar), está quieta (es impar) o disminuye (es par). Mi publicación anterior sobre el tema se cerró debido a que mi pregunta no estaba clara.

Descubrí que si puedo escribir un artículo sobre esto (o conseguir que alguien me ayude a escribirlo, ayudándome con la terminología y demás), podríamos representar el ( 3 norte + 1 ) Collatz-problema con un Autómata Celular (o Autómata Celular Adaptativo), y alguien podría abordar el problema desde ese punto de vista; como por ejemplo, Matthew Cook demostró que la Regla 110 era Turing Completa (es decir, universal); y un estudiante universitario del Reino Unido demostró que un 2 , 3 La máquina de Turing era universal. Tengo la sensación de que tal vez podamos averiguar si la conjetura es verdadera, falsa o indemostrable resolviendo algunas propiedades de este autómata.

Como ahora la Conjetura de Collatz se representa como un Autómata Celular, creo que podemos hacer una o más conjeturas; uno que indirectamente prueba o refuta la conjetura, o uno que nos da alguna información sobre su comportamiento o si es indecidible. No he podido llegar a la comunidad matemática con mi Cellular Automaton sobre la conjetura de Collatz, y no sé si ya existe (es decir, si alguien más ya lo ha hecho), todavía no he encontrado un papel que se ve similar a mi representación (en una red de enteros binarios que usa un vecindario en forma de L-tetromino).

Sobre el autómata: creo que la convergencia es difícil de probar en un autómata celular, pero podría ser posible dependiendo del vecindario, la regla y la configuración de CA, tal vez. Creo que probar que los caminos que toma el vecindario (función de transición) alcanzan algún límite (o no) demostrará que la conjetura es cierta o no. Es difícil para mí describir realmente lo que quiero decir con esto. Por favor, si alguien ha probado esto antes? Me gustaría saber más al respecto. Cualquiera que sepa sobre información, o un documento sobre esto específicamente, me gustaría saber.

Mi pregunta es; ¿Existe ya una conjetura sobre el Collatz en forma de un autómata celular, y tal que si se puede probar que algo sobre él es verdadero o falso, también probará si la conjetura original es verdadera o falsa?

Gracias

Ejemplo de diagrama de espacio-tiempo del autómata celular que muestra solo números impares (omitiendo la regla de desplazamiento a la derecha):

ingrese la descripción de la imagen aquí

Es posible que ya haya intentado una búsqueda en Google y haya encontrado, por ejemplo, la pregunta 11611 de CS StackExchange "¿Cuál es el problema 'más cercano' a la conjetura de Collatz que se resolvió con éxito?".
No, estas cosas son de interés. Gracias.
FWIW, esto todavía no está claro: ha unido las palabras 'conjetura de Collatz' y 'autómata celular', pero en realidad no ha definido su autómata ni ha explicado cómo cree que modela el problema de Collatz. Ser mucho más específico, posiblemente con un ejemplo, sería realmente útil aquí.
Lo siento. Trataré de describirlo mejor mañana ya que me voy a dormir pronto. Sin embargo, puedo describirlo brevemente con algunas palabras aquí primero. Modela el problema de Collatz de esta manera: cada configuración que genera la CA produce el siguiente entero en secuencia. Por valores binarios, al igual que la regla 110, produce una salida en el lado izquierdo, por lo que el bit más significativo está en el extremo izquierdo donde se encuentra el último bit '1'. Como cualquier otra función de Collatz, cada iteración es igual a cada configuración de CA. La CA es un vecindario de 2 estados y 4 estados (en forma de L con 2 estados de tiempo al mismo tiempo).
Es solo una de las 65536 reglas que producen (3n+1) secuencia de Collatz. Entonces la función de transición de estado es única. Pero cuando la salida es par, la regla cambia para cambiar la regla a la derecha, de modo que los números pares siempre transitan a números impares. por lo tanto, hay un borde de estado '1' en el lado derecho (similar a la regla 110 con una celda negra). Tenemos que cambiar la función de transición cuando la configuración (bit menos significativo) tiene una paridad diferente. Pero el autómata es bastante simple en ese sentido.
@NaturalNumberGuy 'Simple', pero eso hace que deje de ser un autómata celular. De hecho, no creo que haya una CA que pueda operar en la representación binaria de un número norte para producir norte + 1 , por una razón sutil pero vital: las CA por su naturaleza son de operación local ; el valor de una celda en una nueva generación solo puede depender de los valores de una vecindad finita fija de celdas en la(s) generación(es) anterior(es). Pero operaciones como la suma y la multiplicación (sin potencia de dos) son innatamente no locales en representaciones binarias; pueden depender de bits arbitrariamente lejanos. (Considere 111111+1)
@Steven Stadnicki: Depende de cómo configure su CA. Sé que es local en operación, pero la misma regla se aplica en la red "completa". Hice un sumador binario con carry una vez usando las mismas ideas. Ya sea que uno lo llame CA, Turing Machine o lo que sea, no importa, lo que importa son las operaciones que uno hace. Parece que nadie me cree. 3 norte + 1 es simple, ya di una descripción aproximada de cómo lo hice. Se hace como cualquier otra operación booleana, obtienes algunas puertas lógicas booleanas de la regla. Sin embargo, es difícil escribir un artículo al respecto, porque siento que el texto debe ser más formal.

Respuestas (1)

El problema de Collatz se puede mapear aún más simplemente a un autómata celular usando base 6, porque la división por 2 en base 6 es extremadamente similar a la multiplicación por 3, y no hay problema de acarreos en cascada. Es bastante fácil crear un autómata de 7 estados cuya vecindad sea simplemente dos celdas adyacentes en la generación anterior. Los 7 estados corresponden a los 6 dígitos de base 6, y un estado nulo para marcar los bordes del cómputo. Alguien codificó una representación de autómata celular de base 6 de la conjetura de Collatz en wolfram.com en 2011: https://demonstrations.wolfram.com/CollatzProblemAsACellularAutomaton/

Autómatas celulares en la conjetura de Collatz
RespuestasAquíPolítica de privacidad1y, 0v