Inexpressibility in Exp-Minus-Log

Resumo Técnico: Inexpressibilidade em Exp-Minus-Log

Enunciado do Problema
O artigo aborda uma lacuna na compreensão teórica do sistema Exp-Minus-Log (EML), originalmente definido por Odrzywo lek [4]. Este sistema reduz todas as funções elementares, constantes e operações sobre números complexos a um único operador binário, $E(\alpha, \beta) = \exp(\alpha) - \log(\beta)$, e à constante '1'. Embora o trabalho de Odrzywo lek fosse amplamente construtivo e existencial — demonstrando como expressar funções elementares padrão —, não estabeleceu um teorema formal de inexpressibilidade. Especificamente, permaneceu uma questão em aberto se o sistema EML poderia expressar números reais não computáveis. Este artigo busca caracterizar os limites da expressibilidade do EML determinando o status de computabilidade de todos os números representáveis dentro do sistema.

Metodologia
Os autores empregam uma combinação de lógica formal, análise computável e teoria da informação algorítmica para estabelecer os limites do EML. A metodologia procede em três etapas lógicas:

1. Equivalência Formal: O artigo estabelece primeiro uma equivalência rigorosa entre os números EML de Odrzywo lek e os números EL de Chow [2]. Ao fornecer substituições sintáticas explícitas, os autores demonstram que o corpo dos números EML é idêntico ao corpo dos números EL (o menor subcorpo de $\mathbb{C}$ fechado sob $\exp$ e $\log$).
2. Análise de Computabilidade: Aproveitando resultados da análise computável (especificamente [7] e [6]), os autores analisam a computabilidade das operações envolvidas. Eles utilizam o fato de que a função exponencial é computável em todas as entradas complexas computáveis. Para o logaritmo, abordam as questões do corte de ramo provando que, para qualquer expressão EML definida, o argumento do logaritmo ou está sobre o eixo real negativo (onde o valor é computável via magnitude e $\pi$) ou está limitado a uma distância racional do corte de ramo.
3. Prova Indutiva de Computabilidade: Usando indução estrutural na sintaxe das expressões EML, os autores provam que toda expressão EML definida avalia-se para um número complexo computável.
4. Seleção de Testemunha: Para demonstrar a inexpressibilidade, o artigo utiliza $\Omega_U$ de Chaitin (a probabilidade de parada de uma máquina de Turing universal prefixada) como uma testemunha canônica. Sabe-se que $\Omega_U$ é enumerável à esquerda computavelmente, mas não computável.

Principais Contribuições e Resultados
O artigo produz os seguintes resultados primários:

• Teorema de Equivalência: O conjunto de números expressíveis via EML é provado ser exatamente o conjunto dos números EL de Chow ($EML = EL$).
• Teorema de Computabilidade: O artigo prova que todo número expressível via EML é computável. Especificamente, para qualquer expressão EML fechada $\phi$ onde o valor é definido, $[[\phi]]$ é um número complexo computável. Consequentemente, o conjunto dos reais construíveis via EML ($EML_{\mathbb{R}}$) é um subconjunto dos reais computáveis ($\text{Comp}_{\mathbb{R}}$).
• Teorema de Inexpressibilidade: Ao combinar a computabilidade dos números EML com a não computabilidade de $\Omega_U$ de Chaitin, o artigo prova formalmente que $\Omega_U \notin EML_{\mathbb{R}}$.
• Implicação Teórica de Medida: Como o conjunto dos números EML é enumerável (devido à enumerabilidade da sintaxe), o conjunto dos reais não expressíveis via EML possui medida de Lebesgue total em $\mathbb{R}$. Isso inclui não apenas $\Omega_U$, mas também outras classes de números não computáveis, como a expansão binária do conjunto de parada, limites de sequências de Specker e reais aleatórios de Martin-Löf.

Significado e Alegações
O artigo afirma preencher uma lacuna teórica específica deixada pelo trabalho original de Odrzywo lek, fornecendo um teorema formal de inexpressibilidade para o sistema EML. O significado reside em caracterizar o sistema EML não apenas como uma ferramenta para gerar funções elementares, mas como um sistema estritamente limitado pela computabilidade.

Os autores enquadram modestamente o resultado como uma limitação formal: embora o EML seja esteticamente agradável e útil para computação simbólica e aritmética exata (como notado na introdução a respeito de sistemas de álgebra computacional), ele não pode expressar os reais não computáveis "canônicos". O artigo não propõe novas aplicações ou propostas experimentais; ao contrário, serve como uma prova fundamental estabelecendo que $EML_{\mathbb{R}} \subsetneq \mathbb{R}$ e, mais especificamente, $EML_{\mathbb{R}} \subseteq \text{Comp}_{\mathbb{R}}$. O resultado confirma que os números de "forma fechada" expressíveis via este único operador estão estritamente limitados ao reino dos números computáveis.