Inexpressibility in Exp-Minus-Log

Resumen Técnico: Inexpresabilidad en Exp-Minus-Log

Enunciado del Problema
El artículo aborda una brecha en la comprensión teórica del sistema Exp-Minus-Log (EML), definido originalmente por Odrzywo lek [4]. Este sistema reduce todas las funciones elementales, constantes y operaciones sobre números complejos a un único operador binario, $E(\alpha, \beta) = \exp(\alpha) - \log(\beta)$, y a la constante '1'. Si bien el trabajo de Odrzywo lek fue en gran medida constructivo y existencial —demostrando cómo expresar funciones elementales estándar—, no estableció un teorema formal de inexpresabilidad. Específicamente, permaneció como una pregunta abierta si el sistema EML podía expresar números reales no computables. Este artículo busca caracterizar los límites de la expresabilidad de EML determinando el estado de computabilidad de todos los números representables dentro del sistema.

Metodología
Los autores emplean una combinación de lógica formal, análisis computable y teoría de la información algorítmica para establecer los límites de EML. La metodología procede en tres etapas lógicas:

1. Equivalencia Formal: El artículo establece primero una equivalencia rigurosa entre los números EML de Odrzywo lek y los números EL de Chow [2]. Al proporcionar sustituciones sintácticas explícitas, los autores demuestran que el cuerpo de números EML es idéntico al cuerpo de números EL (el subcuerpo más pequeño de $\mathbb{C}$ cerrado bajo $\exp$ y $\log$).
2. Análisis de Computabilidad: Aprovechando resultados del análisis computable (específicamente [7] y [6]), los autores analizan la computabilidad de las operaciones involucradas. Utilizan el hecho de que la función exponencial es computable en todas las entradas complejas computables. Para el logaritmo, abordan los problemas del corte de rama demostrando que, para cualquier expresión EML definida, el argumento del logaritmo o bien yace sobre el eje real negativo (donde el valor es computable mediante magnitud y $\pi$) o está acotado lejos del corte de rama por una distancia racional.
3. Prueba Inductiva de Computabilidad: Mediante inducción estructural sobre la sintaxis de las expresiones EML, los autores prueban que toda expresión EML definida evalúa a un número complejo computable.
4. Selección de Testigo: Para demostrar la inexpresabilidad, el artículo utiliza $\Omega_U$ de Chaitin (la probabilidad de parada de una máquina de Turing universal sin prefijos) como un testigo canónico. Se sabe que $\Omega_U$ es enumerable computablemente por la izquierda pero no computable.

Contribuciones y Resultados Clave
El artículo produce los siguientes resultados principales:

• Teorema de Equivalencia: Se demuestra que el conjunto de números expresables en EML es exactamente el conjunto de los números EL de Chow ($EML = EL$).
• Teorema de Computabilidad: El artículo demuestra que todo número expresable en EML es computable. Específicamente, para cualquier expresión EML cerrada $\phi$ donde el valor está definido, $[[\phi]]$ es un número complejo computable. En consecuencia, el conjunto de reales construibles en EML ($EML_{\mathbb{R}}$) es un subconjunto de los reales computables ($\text{Comp}_{\mathbb{R}}$).
• Teorema de Inexpresabilidad: Al combinar la computabilidad de los números EML con la no computabilidad del $\Omega_U$ de Chaitin, el artículo demuestra formalmente que $\Omega_U \notin EML_{\mathbb{R}}$.
• Implicación Teórica de la Medida: Dado que el conjunto de números EML es numerable (debido a la numerabilidad de la sintaxis), el conjunto de reales no expresables en EML tiene medida de Lebesgue completa en $\mathbb{R}$. Esto incluye no solo a $\Omega_U$, sino también a otras clases de números no computables, como la expansión binaria del conjunto de parada, límites de secuencias de Specker y reales aleatorios de Martin-Löf.

Significado y Afirmaciones
El artículo afirma llenar una brecha teórica específica dejada por el trabajo original de Odrzywo lek al proporcionar un teorema formal de inexpresabilidad para el sistema EML. El significado radica en caracterizar el sistema EML no solo como una herramienta para generar funciones elementales, sino como un sistema estrictamente acotado por la computabilidad.

Los autores enmarcan modestamente el resultado como una limitación formal: si bien EML es estéticamente agradable y útil para el cálculo simbólico y la aritmética exacta (como se señala en la introducción respecto a los sistemas de álgebra computacional), no puede expresar los reales no computables "canónicos". El artículo no propone nuevas aplicaciones ni propuestas experimentales; más bien, sirve como una prueba fundacional que establece que $EML_{\mathbb{R}} \subsetneq \mathbb{R}$ y, más específicamente, $EML_{\mathbb{R}} \subseteq \text{Comp}_{\mathbb{R}}$. El resultado confirma que los números de "forma cerrada" expresables mediante este único operador están estrictamente limitados al reino de los números computables.