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

1. O Problema

O artigo investiga a existência e a decidibilidade de sistemas aditivos para o conjunto dos inteiros ($\mathbb{Z}$). Um sistema aditivo é definido como uma coleção de subconjuntos $A = \{A_0, A_1, \dots\}$ de um monóide aditivo $M$ (neste caso, $\mathbb{Z}$) tal que todo elemento $n \in M$ possui uma e apenas uma representação como uma soma finita $n = a_0 + a_1 + \dots + a_k$, onde $a_i \in A_i$.

Enquanto o problema para os inteiros não negativos ($\mathbb{N}_0$) foi completamente resolvido pelo Teorema de de Bruijn (que caracteriza tais sistemas como contrações de "sistemas numéricos britânicos"), o caso para $\mathbb{Z}$ permanece notoriamente difícil e sem uma caracterização completa. O objetivo central do artigo é determinar se, dada uma coleção específica de conjuntos, é possível decidir algoritmicamente se ela forma um sistema aditivo completo para $\mathbb{Z}$.

2. Metodologia

O autor emprega uma abordagem interdisciplinar que combina combinatória aditiva e sistemas dinâmicos. A metodologia segue os seguintes passos:

• Definição de Coleções Canônicas: O autor introduz o conceito de "coleções canônicas", que generalizam sistemas numéricos (como o sistema decimal ou ternário balanceado) para $\mathbb{Z}$. Uma coleção canônica é definida por sequências de bases $(b_i)$ e sistemas de resíduos completos $(T_i)$, gerando conjuntos da forma $A_i = (b_0 \dots b_{i-1})T_i$.
• Tradução para Sistemas Dinâmicos: O problema de determinar se um número $n \in \mathbb{Z}$ pertence à soma direta da coleção é traduzido para a dinâmica de um sistema não autônomo. A representação de $n$ é equivalente à iteração de uma sequência de mapas $f_i(n)$, onde cada $f_i$ remove um "dígito" de $n$ em uma base específica e ajusta o restante.
• Correspondência com Trajetórias: O autor estabelece que uma coleção canônica é completa (ou seja, cobre todo $\mathbb{Z}$) se e somente se a trajetória de todo inteiro $n$ no sistema dinâmico associado eventualmente se torne zero (estacionária).
• Redução de Problemas: O autor constrói coleções canônicas específicas cujas propriedades de completude são equivalentes a problemas computacionais famosos e indecidíveis:
  1. A Conjectura de Collatz.
  2. O Problema de Halting Universal para a linguagem de programação Fractran (introduzida por John Conway).

3. Contribuições Chave

• Generalização Estrutural: A definição de "coleções canônicas" fornece uma estrutura unificada que engloba exemplos conhecidos de sistemas aditivos para $\mathbb{Z}$ (como o sistema negabinario e o ternário balanceado) e generaliza os sistemas numéricos de base variável de de Bruijn para o domínio dos inteiros.
• Equivalência com Collatz: O artigo prova que existe uma coleção canônica específica ($A_C$) tal que ela é um sistema aditivo completo para $\mathbb{Z}$ se e somente se a Conjectura de Collatz for verdadeira. Isso conecta diretamente um problema de combinatória aditiva a um dos problemas em aberto mais famosos da matemática.
• Indecidibilidade via Fractran: O autor demonstra que, para uma subclasse bem-comportada de coleções canônicas (chamadas de "tipo Fractran"), a questão de saber se a coleção é completa é equivalente ao problema de halting universal para programas Fractran.
• Teorema Principal: A conclusão fundamental é que não existe um algoritmo geral que possa decidir, para qualquer coleção canônica dada, se ela forma um sistema aditivo para $\mathbb{Z}$.

4. Resultados Principais

• Teorema 1: Existe uma coleção canônica $A_C$ definida por bases e resíduos específicos que codifica a dinâmica de Collatz. $A_C$ é completa $\iff$ a Conjectura de Collatz é verdadeira.
• Teorema 2: Para qualquer programa Fractran $F$, pode-se construir uma coleção canônica $A_F$ (tipo Fractran) tal que $A_F$ é completa $\iff$ o programa $F$ para para todas as entradas.
• Corolário 2: O problema de determinar se uma coleção canônica do tipo Fractran é completa é indecidível. Isso implica que não há procedimento algorítmico geral para verificar a completude de sistemas aditivos para $\mathbb{Z}$.
• Não-análogo de de Bruijn: O artigo mostra que, ao contrário do caso de $\mathbb{N}_0$, não existe um teorema de caracterização simples (como contrações de sistemas britânicos) para todos os sistemas aditivos de $\mathbb{Z}$, pois existem sistemas aditivos que não são contrações de coleções canônicas.

5. Significado e Impacto

O trabalho tem implicações profundas em várias áreas:

• Teoria dos Números e Combinatória: Revela a complexidade intrínseca e a natureza "selvagem" dos sistemas aditivos em $\mathbb{Z}$, mostrando que propriedades aparentemente simples (cobrir todos os inteiros com representações únicas) podem esconder problemas computacionais indecidíveis.
• Teoria da Computabilidade: Estabelece uma ponte direta entre problemas de tiling (pavimentação) e somas diretas em grupos abelianos e a indecidibilidade computacional. Mostra que a estrutura algébrica de $\mathbb{Z}$ permite codificar a lógica de máquinas de Turing (via Fractran) dentro de problemas de decomposição aditiva.
• Sistemas Dinâmicos: Oferece uma nova perspectiva sobre a Conjectura de Collatz, enquadrando-a como um problema de completude de um sistema aditivo, sugerindo que a dificuldade do problema reside na estrutura global da dinâmica, e não apenas na aritmética local.

Em resumo, Zabolotskii demonstra que a pergunta "esta coleção de conjuntos gera todos os inteiros de forma única?" é, em geral, uma questão indecidível, elevando o estudo de sistemas aditivos para $\mathbb{Z}$ a um novo patamar de complexidade teórica.