Shannon meets Gödel-Tarski-Löb: Undecidability of Shannon Feedback Capacity for Finite-State Channels

Resumen Técnico: Indecidibilidad de la Capacidad de Retroalimentación en Canales de Estado Finito

1. El Problema

El artículo aborda el problema de decisión exacto para la capacidad de retroalimentación ($C_{fb}$) en canales de estado finito (FSC, por sus siglas en inglés). Específicamente, se plantea la siguiente cuestión:

Dada una codificación efectiva $e$ de un canal de estado finito unifilar con entradas y salidas binarias, cuyos parámetros (probabilidades de transición y distribución inicial) son racionales, y dado un umbral racional $q \in \mathbb{Q}$, ¿es posible determinar algorítmicamente si la capacidad de retroalimentación exacta satisface la desigualdad:
$$C_{fb}(W_e, \pi_{1,e}) \geq q$$

El enfoque del trabajo es estrictamente sobre la exactitud (sin aproximaciones, sin horizontes finitos y sin brechas de promesa). El objetivo es saber si existe un algoritmo universal que pueda decidir esta propiedad para toda la clase de canales especificada.

2. Metodología y Construcción

El autor, Angshul Majumdar, emplea una combinación de teoría de la información, teoría de la computabilidad y lógica matemática. La metodología se estructura en los siguientes pasos clave:

• Clase de Canales Restringida: El análisis se limita a una clase muy específica de canales:
  • Entradas y salidas binarias ($\{0, 1\}$).
  • Estado finito y parámetros racionales.
  • Propiedad unifilar: La evolución del estado es determinista dado el estado actual, la entrada y la salida ($S_{t+1} = f(S_t, X_t, Y_t)$).
  • Distribución inicial racional.
• Construcción de "Activación Retardada" (Delayed-Activation):
  • Se construye una familia de canales paramétrica por un entero $N$.
  • Estos canales tienen una fase de "retraso" de $N+1$ pasos donde la salida es determinista (siempre 0) y no aporta información.
  • Después de este retraso, el canal entra en un estado absorbente ($\star$).
  • Se definen dos variantes:
    1. Canal "Bueno" ($Ch_{good}$): En el estado $\star$, el canal es libre de ruido ($Y_t = X_t$). Su capacidad asintótica es 1.
    2. Canal "Malo" ($Ch_{bad}$): En el estado $\star$, el canal es completamente ruidoso (salida independiente de la entrada). Su capacidad asintótica es 0.
• Reducción de Indecidibilidad:
  • Se demuestra que, para cualquier horizonte finito $n \leq N+1$, ambos canales tienen un valor de información dirigida idéntico (cero).
  • Sin embargo, sus capacidades asintóticas ($n \to \infty$) son radicalmente diferentes (1 vs 0).
  • Mediante una reducción many-one desde un problema indecidible conocido (como el problema de la parada o un lenguaje recursivamente enumerable no decidible), se demuestra que determinar si la capacidad supera un umbral $q$ es equivalente a resolver ese problema indecidible.

3. Contribuciones Clave y Resultados

El artículo establece cuatro resultados fundamentales:

1. Indecidibilidad de la Decisión Exacta:

   • Teorema IV.4: No existe ningún algoritmo que pueda decidir si $C_{fb}(W_e, \pi_{1,e}) \geq q$ para la clase de canales unifilares racionales descrita. El lenguaje de decisión $L_{Cap}$ es indecidible.
   • Esto implica que la capacidad de retroalimentación exacta no es computable, incluso en sistemas con parámetros racionales y estructura determinista simple.

2. Barrera Algebraica Real ($\exists\mathbb{R}$):

   • Teorema V.7: El problema de decisión no pertenece a la clase de complejidad $\exists\mathbb{R}$ (Teoría Existencial de los Reales).
   • Esto significa que no existe una reducción universal del problema de capacidad a un sistema finito de ecuaciones e inecuaciones polinómicas sobre los números reales. A diferencia de muchos problemas geométricos exactos que son decidibles (en PSPACE), este problema es intrínsecamente más complejo.

3. Imposibilidad de Caracterización de Horizonte Finito:

   • Corolario IV.7: No existe una caracterización uniforme de horizonte finito. Es decir, no hay un funcional $\Psi$ que dependa solo de un número fijo de valores de información dirigida ($V_1, \dots, V_N$) que pueda recuperar la capacidad asintótica exacta para todos los canales en la clase.
   • La convergencia de la secuencia de valores finitos no garantiza la determinación del límite asintótico en tiempo finito.

4. Consecuencias Lógicas (Gödel-Tarski-Löb):

   • Sección VI: Al codificar la verdad de la capacidad como un predicado aritmético, se derivan consecuencias metateóricas para cualquier teoría formal recursivamente axiomatizable que intente razonar sobre estas capacidades:
     • Incompleteness (Gödel): Ninguna teoría efectiva y consistente puede decidir todos los enunciados sobre umbrales de capacidad.
     • Indefinibilidad (Tarski): La verdad semántica de la capacidad no puede definirse dentro de la propia teoría.
     • Obstrucción de Löb: No existe un principio de reflexión uniforme que permita a la teoría certificar la corrección de sus propias pruebas sobre umbrales de capacidad.

4. Significado e Implicaciones

• Límites Fundamentales: El resultado no es una limitación técnica actual, sino una barrera fundamental. Establece que no se puede esperar un algoritmo universal ni una fórmula de "letra única" (single-letter formula) exacta para la capacidad de retroalimentación en canales de estado finito generales.
• Clarificación del Estado del Arte: El trabajo no invalida los resultados positivos existentes para subclases estructuradas (como canales con propiedades de contracción o mezclado específicas), ni descarta métodos de aproximación o optimización de horizonte finito. Más bien, delimita la frontera entre lo que es posible en subclases estructuradas y lo que es imposible en la generalidad.
• Cambio de Paradigma: Sugiere que el progreso futuro en la teoría de capacidad de retroalimentación debe centrarse en:
  • Identificar subclases más restringidas donde la decidibilidad se recupera.
  • Desarrollar esquemas de aproximación con garantías de error controlado.
  • Reconocer que la "verdad" exacta de la capacidad puede ser inalcanzable formalmente en sistemas suficientemente expresivos.

En conclusión, el artículo demuestra que la capacidad de retroalimentación exacta en canales de estado finito es un problema indecidible, conectando la teoría de la información con las limitaciones fundamentales de la lógica matemática y la computabilidad.