Additive systems for $\mathbb{Z}$ are undecidable

1. El Problema

El artículo aborda la cuestión fundamental en la teoría de sistemas aditivos: ¿Cuáles son las colecciones de subconjuntos $A_i \subset \mathbb{Z}$ tales que cualquier entero $n \in \mathbb{Z}$ tiene exactamente una representación como una suma finita $n = a_0 + a_1 + \dots$, donde $a_i \in A_i$?

• Contexto en $\mathbb{N}_0$: Para los enteros no negativos, este problema está completamente resuelto gracias al Teorema de de Bruijn (1956). Este teorema establece que cualquier sistema aditivo para $\mathbb{N}_0$ es una contracción de un "sistema numérico británico" (una generalización de los sistemas de numeración con bases variables, como el sistema decimal o el sistema de pesos británico).
• El Desafío en $\mathbb{Z}$: Para el conjunto de los enteros $\mathbb{Z}$, el problema es significativamente más difícil y carecía de una caracterización completa. La literatura existente se ha centrado principalmente en sistemas de cardinalidad 2 ($\mathbb{Z} = A \oplus B$) o en casos con estructuras muy específicas. El autor señala que, a diferencia de $\mathbb{N}_0$, no existe un análogo directo del teorema de de Bruijn para $\mathbb{Z}$, y determinar si una colección dada cubre todo $\mathbb{Z}$ de manera única es un problema abierto y complejo.

2. Metodología

El autor emplea una metodología interdisciplinaria que combina la combinatoria aditiva con la teoría de sistemas dinámicos.

1. Definición de Colecciones Canónicas:
   Se introduce una nueva clase de estructuras llamadas colecciones canónicas. Estas generalizan los sistemas de numeración para $\mathbb{Z}$. Una colección canónica se define por dos secuencias:

   • Una secuencia de bases $(b_i)_{i \in \mathbb{N}_0}$ con $b_i > 1$.
   • Una secuencia de conjuntos $(T_i)_{i \in \mathbb{N}_0}$, donde cada $T_i$ es un sistema completo de residuos módulo $b_i$ que incluye al 0.
     La colección de conjuntos es $A = \{T_0, b_0 T_1, b_0 b_1 T_2, \dots\}$.

2. Traducción a Sistemas Dinámicos:
   El núcleo de la metodología es reinterpretar el problema de la completitud de una colección canónica como un problema de dinámica.

   • Se define un sistema canónico asociado a la colección como una secuencia de mapas $f_i: \mathbb{Z} \to \mathbb{Z}$.
   • La expansión de un entero $n$ en el sistema se calcula mediante una trayectoria iterativa: $n_{i+1} = f_i(n_i) = \frac{1}{b_i}(n_i - t_i(n_i))$, donde $t_i(n_i)$ es el elemento único de $T_i$ congruente con $n_i$ módulo $b_i$.
   • Proposición Clave: Una colección canónica es un sistema aditivo para $\mathbb{Z}$ (es decir, es "completa") si y solo si la trayectoria de todo entero $n$ en el sistema canónico asociado converge eventualmente a la constante cero.

3. Reducción a Problemas de Indecidibilidad:
   Utilizando esta correspondencia dinámica, el autor construye colecciones canónicas específicas cuya trayectoria imita el comportamiento de problemas computacionales conocidos por ser indecidibles o abiertos.

3. Contribuciones Clave

• Introducción de Colecciones Canónicas: Se define formalmente una familia natural de candidatos para sistemas aditivos en $\mathbb{Z}$ que unifica ejemplos conocidos (como el sistema binario negativo y el ternario balanceado) bajo un marco general.
• Puente entre Combinatoria y Dinámica: Se establece una equivalencia rigurosa entre la propiedad de "completitud" de un sistema aditivo y la convergencia de trayectorias en un sistema dinámico no autónomo.
• Construcciones de Equivalencia:
  • Se demuestra que la pregunta de si una colección canónica específica es completa es equivalente a la Conjetura de Collatz.
  • Se demuestra que, para una subfamilia bien comportada (colecciones de tipo Fractran), la pregunta de completitud es equivalente al Problema de Halting Universal para el lenguaje de programación Fractran.

4. Resultados Principales

El artículo presenta tres resultados teóricos fundamentales:

• Teorema 1 (Equivalencia con Collatz): Existe una colección canónica $A_C$ tal que $A_C$ es un sistema aditivo completo para $\mathbb{Z}$ si y solo si la Conjetura de Collatz es verdadera.

  • Mecanismo: Se construye una colección donde las bases $b_i$ y los conjuntos $T_i$ están diseñados para que la trayectoria de un número $n$ simule exactamente la secuencia de Collatz ($3n+1$ si es impar, $n/2$ si es par). Si la conjetura es cierta, todas las trayectorias llegan a 1 y luego a 0 (completitud). Si falla, existe una trayectoria que no converge a 0, y la colección no es completa.

• Teorema 2 (Equivalencia con Fractran): Para cualquier programa Fractran $F$, se puede construir una colección canónica de tipo Fractran $A_F$ tal que $A_F$ es completa si y solo si el programa $F$ se detiene para todas las entradas posibles.

  • Mecanismo: Se utiliza la capacidad de cómputo universal de Fractran. La colección se define de modo que la dinámica de sus mapas $f_i$ replique la ejecución de instrucciones de Fractran.

• Corolario 2 (Indecidibilidad): El problema de determinar si una colección canónica de tipo Fractran dada es completa es indecidible.

  • Dado que el problema de halting universal para Fractran es indecidible (no existe un algoritmo que pueda determinar si un programa arbitrario se detiene para todas las entradas), tampoco existe un algoritmo para determinar si una colección canónica de este tipo es un sistema aditivo completo.

5. Significado e Impacto

• Resolución de la Complejidad del Problema: El trabajo demuestra que el problema de caracterizar sistemas aditivos para $\mathbb{Z}$ es inherentemente complejo. No es solo un problema difícil de resolver, sino que, para ciertas familias naturales de candidatos, es indecidible. Esto implica que no puede existir un algoritmo general que verifique la completitud de cualquier colección canónica.
• Conexión con Problemas Abiertos: Al vincular la completitud de sistemas aditivos con la Conjetura de Collatz, el artículo sugiere que la resolución de este problema de teoría de números podría requerir avances en la comprensión de sistemas dinámicos no autónomos, y viceversa.
• Nueva Perspectiva Teórica: La traducción de problemas de combinatoria aditiva a sistemas dinámicos ofrece una nueva herramienta poderosa para analizar la estructura de los enteros. Muestra que la "estructura" esperada en sistemas aditivos infinitos puede ser tan caótica como los problemas computacionales más difíciles.
• Limitación de Generalizaciones: El resultado refuerza la idea de que, a diferencia de $\mathbb{N}_0$ (donde de Bruijn proporcionó una caracterización completa), para $\mathbb{Z}$ no existe una teoría unificada simple; la naturaleza de los sistemas aditivos en los enteros está intrínsecamente ligada a la indecidibilidad computacional.

En resumen, el artículo de Zabolotskii transforma una pregunta de teoría de números sobre la representación única de enteros en un problema de dinámica y computabilidad, demostrando que la respuesta a esta pregunta es, en el caso general, imposible de determinar algorítmicamente.