Límites de la Computación: El Halting Problem

El primer problema demostrado como indecidible.

Introducción: ¿Hay Límites?

Hasta ahora hemos visto qué pueden hacer las Máquinas de Turing. Ahora la pregunta opuesta:

¿Hay problemas que ninguna Máquina de Turing puede resolver?

Respuesta sorprendente: ¡SÍ!

Y no son problemas esotéricos — son preguntas muy prácticas:

¿Este programa tiene un bug?
¿Este código se detiene o hace loop infinito?
¿Estos dos programas hacen lo mismo?

La Técnica: Diagonalización

Antes de ver el Halting Problem, necesitamos entender una técnica poderosa: diagonalización.

Idea de Cantor: No Todos los Infinitos son Iguales

Pregunta: ¿Hay más números reales que naturales?

Intuición: Ambos son infinitos, ¿cómo comparar?

Respuesta de Cantor (1891):

Definición: Dos conjuntos tienen el mismo “tamaño” si hay una biyección entre ellos.

$\mathbb{N}$ (naturales) es numerable (contable)
$\mathbb{Q}$ (racionales) también es numerable (¡sorpresa!)
$\mathbb{R}$ (reales) es NO numerable (más grande)

Demostración por Diagonalización (sketch)

Supongamos que $\mathbb{R}$ entre 0 y 1 es numerable. Entonces podemos listar todos los reales:

1: 0.1415926...
2: 0.7182818...
3: 0.5772156...
4: 0.1234567...
⋮

Construcción diagonal: Crear un número $d$ que difiere de todos:

Difiere del 1er número en el 1er dígito
Difiere del 2do número en el 2do dígito
Difiere del n-ésimo número en el n-ésimo dígito

d = 0.2ₐ8ₐ6ₐ7...
       ↑  ↑  ↑
       Difiere en posición 1, 2, 3, ...

Conclusión: $d$ no está en la lista → ¡contradicción! Los reales no son numerables.

Pattern clave: “Usar algo contra sí mismo” para crear contradicción.

El Halting Problem

Definición del Problema

El Halting Problem pregunta:

Dada una Máquina de Turing $M$ y una entrada $w$, ¿$M$ se detiene cuando ejecutamos $M(w)$?

Formalmente, queremos decidir el lenguaje:

$$\text{HALT} = {\langle M, w \rangle \mid M \text{ es una MT que se detiene en entrada } w}$$

Ejemplos:

MT	Entrada	¿Se detiene?
MT que acepta $0^n1^n$	“0011”	✓ Sí (acepta)
MT que acepta $0^n1^n$	“00”	✓ Sí (rechaza)
MT que busca contraejemplo a Goldbach	“cualquier”	? Quién sabe
MT: `while True: pass`	“cualquier”	✗ No (loop infinito)

Teorema Principal: HALT es Indecidible

Teorema: El Halting Problem es indecidible.

Significado: NO existe ninguna Máquina de Turing que siempre termine y decida si una MT arbitraria se detiene.

Demostración (por Contradicción)

Supongamos (para contradicción) que existe un decididor $H$ para HALT.

Es decir, $H$ es una MT que:

$$H(\langle M, w \rangle) = \begin{cases} \text{acepta} & \text{si } M \text{ se detiene en } w \ \text{rechaza} & \text{si } M \text{ hace loop en } w \end{cases}$$

Paso 1: Construir una MT “problemática” llamada $D$ (de “diagonal”):

D en entrada <M>:
1. Ejecutar H(<M>, <M>)    // ¿M se detiene en su propia descripción?
2. Si H acepta (M se detiene):
      hacer LOOP infinito
3. Si H rechaza (M hace loop):
      DETENER (aceptar)

En resumen:

$$D(\langle M \rangle) = \begin{cases} \text{loop} & \text{si } M \text{ se detiene en } \langle M \rangle \ \text{detiene} & \text{si } M \text{ hace loop en } \langle M \rangle \end{cases}$$

$D$ hace lo opuesto a lo que $M$ hace cuando se ejecuta sobre sí misma.

Paso 2: Ejecutar $D$ sobre su propia descripción: $D(\langle D \rangle)$

Pregunta: ¿$D$ se detiene en $\langle D \rangle$?

Caso 1: Supongamos que $D$ se detiene en $\langle D \rangle$

Entonces $H(\langle D, \langle D \rangle \rangle)$ acepta
Por construcción de $D$, si $H$ acepta, $D$ hace loop
Pero asumimos que $D$ se detiene → contradicción ✗

Caso 2: Supongamos que $D$ hace loop en $\langle D \rangle$

Entonces $H(\langle D, \langle D \rangle \rangle)$ rechaza
Por construcción de $D$, si $H$ rechaza, $D$ se detiene
Pero asumimos que $D$ hace loop → contradicción ✗

Conclusión: ¡Ambos casos llevan a contradicción!

Por lo tanto, nuestra suposición inicial es falsa: no puede existir $H$.

$$\boxed{\text{El Halting Problem es indecidible}}$$

Visualización del Argumento

Supongamos H existe:

┌────────────────────────┐
│   Decididor H          │
│                        │
│  Input: <M>, <w>       │
│  Output:               │
│   • Acepta si M(w) ↓   │
│   • Rechaza si M(w) ∞  │
└────────────────────────┘
            ↓
Construimos D usando H:

┌────────────────────────┐
│   Máquina D            │
│                        │
│  Input: <M>            │
│  1. Pregunta a H:      │
│     ¿M(<M>) se detiene?│
│  2. Hace lo OPUESTO:   │
│     • Si sí → loop ∞   │
│     • Si no → detiene ↓│
└────────────────────────┘
            ↓
Ejecutamos D(<D>):

    D(<D>)
       ↓
   ¿Se detiene?
    /        \
  SÍ         NO
   ↓          ↓
Entonces   Entonces
D hace     D se
loop ∞     detiene ↓
   ↓          ↓
¡Pero      ¡Pero
asumimos   asumimos
que se     que hace
detiene!   loop!
   ↓          ↓
   ✗          ✗

¡Ambas opciones llevan a contradicción!

Por lo tanto, $H$ no puede existir.

Analogía: La Paradoja del Barbero

Esta demostración es similar a la famosa paradoja:

En un pueblo, el barbero afeita a todos y solo a los que no se afeitan a sí mismos.

Pregunta: ¿El barbero se afeita a sí mismo?

Análisis:

Si el barbero se afeita a sí mismo → entonces no debe afeitarse (por definición) → contradicción
Si el barbero no se afeita a sí mismo → entonces debe afeitarse (por definición) → contradicción

Conclusión: ¡Tal barbero no puede existir!

Conexión: El Halting Problem usa la misma estructura lógica — “aplicar algo a sí mismo” para crear contradicción.

HALT es Reconocible (pero no Decidible)

Observación importante: Aunque HALT no es decidible, SÍ es reconocible.

Recordatorio: Un lenguaje es reconocible (o recursivamente enumerable) si existe una Máquina de Turing que:

Acepta todas las entradas que están en el lenguaje (eventualmente)
Rechaza o hace loop en entradas que NO están en el lenguaje
No necesita terminar siempre — solo debe terminar y aceptar cuando la respuesta es “sí”

La diferencia con decidible: un decididor debe terminar siempre (con aceptar o rechazar), mientras que un reconocedor solo debe terminar cuando acepta.

Reconocedor para HALT:

R en entrada <M, w>:
1. Simular M en w
2. Si M se detiene → aceptar
3. Si M hace loop → hacer loop también

Análisis:

Si $\langle M, w \rangle \in \text{HALT}$ (M se detiene) → $R$ acepta ✓
Si $\langle M, w \rangle \notin \text{HALT}$ (M hace loop) → $R$ hace loop

$R$ es un reconocedor pero NO un decididor.

El Complemento de HALT

Consideremos el complemento:

$$\overline{\text{HALT}} = {\langle M, w \rangle \mid M \text{ NO se detiene en } w}$$

Pregunta: ¿Es $\overline{\text{HALT}}$ reconocible?

Respuesta: ¡NO!

Demostración:

Si $\overline{\text{HALT}}$ fuera reconocible, tendríamos:

$\text{HALT}$ es reconocible (ya probado)
$\overline{\text{HALT}}$ es reconocible (suposición)

Por el Teorema de Cierre bajo Complemento:

$$L \text{ decidible} \iff L \text{ y } \overline{L} \text{ reconocibles}$$

Entonces $\text{HALT}$ sería decidible → contradicción con lo que probamos.

Conclusión: $\overline{\text{HALT}}$ ni siquiera es reconocible (está “más allá” de lo computable).

Implicaciones del Halting Problem

Para la Programación

❌ No podemos construir:

Un verificador universal de bugs
Un optimizador que garantice equivalencia
Un detector universal de loops infinitos

Ejemplo práctico: IDEs modernos intentan advertir sobre loops infinitos, pero:

Solo detectan casos obvios
Pueden dar falsos positivos/negativos
Nunca serán perfectos (es imposible)

Para la Verificación de Software

❌ No podemos verificar automáticamente:

“Este programa nunca crashea”
“Este código es seguro”
“Esta función termina para toda entrada”

Soluciones prácticas:

Verificar casos específicos (testing)
Usar heurísticas (análisis estático)
Restricciones al lenguaje (tipos, etc.)
Pruebas formales manuales/asistidas

Para la IA y Agentes

Un agente inteligente no puede:

Predecir el comportamiento de código arbitrario
Verificar propiedades de programas en general
“Entender” completamente código complejo

Implicación: Los sistemas de IA siempre tendrán límites fundamentales.

Otros Problemas Indecidibles

Una vez que sabemos que HALT es indecidible, podemos probar que muchos otros problemas también lo son usando reducciones.

Rice’s Theorem (1951)

Teorema: Cualquier propiedad no trivial sobre el comportamiento de Máquinas de Turing es indecidible.

Propiedad no trivial: No siempre verdadera ni siempre falsa.

Comportamiento: Sobre qué computa la MT (no sobre su estructura).

Ejemplos de propiedades indecidibles:

❌ ¿$L(M)$ está vacío? (¿M no acepta nada?)

❌ ¿$L(M) = \Sigma^*$? (¿M acepta todo?)

❌ ¿$L(M)$ es finito?

❌ ¿$L(M_1) = L(M_2)$? (¿Dos MTs reconocen el mismo lenguaje?)

❌ ¿$M$ acepta al menos 10 strings?

Contraejemplos (propiedades triviales o estructurales):

✓ ¿$M$ tiene 5 estados? (propiedad estructural, decidible)

✓ ¿$L(M) = L(M)$? (siempre verdadera, trivial)

✓ ¿$L(M) \neq \emptyset$ o $L(M) = \emptyset$? (siempre verdadera, trivial)

Implicación: ¡Casi todo lo interesante sobre programas es indecidible!

Post Correspondence Problem (PCP)

Problema: Dadas fichas con dos strings cada una, ¿existe una secuencia de fichas tal que concatenar los strings de arriba = concatenar los de abajo?

Ejemplo:

Fichas:

┌─────┐  ┌─────┐  ┌─────┐
│  a  │  │ ab  │  │ baa │
├─────┤  ├─────┤  ├─────┤
│ baa │  │ aa  │  │  aa │
└─────┘  └─────┘  └─────┘

Solución: Ficha 2, Ficha 1, Ficha 1, Ficha 3

Arriba:  ab  + a   + a   + baa = abaabaa
Abajo:   aa  + baa + baa + aa  = abaabaa

¡Coinciden! ✓

Resultado: PCP es indecidible (se demuestra por reducción desde HALT).

La Técnica: Reducciones

Para probar que un problema $B$ es indecidible:

Tomar un problema $A$ que ya sabemos es indecidible (ej: HALT)
Mostrar que si pudiéramos decidir $B$, podríamos decidir $A$
Como $A$ es indecidible → $B$ también debe serlo

Notación: $A \leq_m B$ (“A se reduce a B”)

Patrón:

Supongamos decididor para B existe:
    ┌──────────┐
    │ Decididor│
    │  para B  │
    └────┬─────┘
         │
    ┌────▼─────────────┐
    │ Transformación   │
    │ de instancia     │
    │ A → instancia B  │
    └────┬─────────────┘
         │
Decididor para A (¡contradicción!)

Ejemplo (sketch): HALT $\leq_m$ “¿$L(M)$ está vacío?”

Si pudiéramos decidir “¿$L(M)$ está vacío?”:

Dada instancia de HALT: $\langle M, w \rangle$
Construir $M’$ que acepta cualquier input sii $M$ se detiene en $w$
$M$ se detiene en $w$ ↔ $L(M’)$ no está vacío
Usar decididor hipotético para “vacío” → decidir HALT
¡Contradicción!

Esta técnica es poderosa — permite probar indecidibilidad de muchos problemas.

Jerarquía Aritmética (avanzado - solo mención)

Los problemas indecidibles tienen diferentes “niveles” de indecidibilidad:

Decidible (Δ₀⁰)
    ↓
Reconocible (Σ₁⁰)  —  HALT
    ↓
Σ₂⁰  —  "¿Existe M que acepta infinitos strings?"
    ↓
Σ₃⁰  —  Problemas más complejos
    ⋮

Esta jerarquía es infinita — hay problemas arbitrariamente “no decidibles”.

Resumen

Concepto	Descripción
Diagonalización	Técnica: usar algo contra sí mismo para contradicción
Halting Problem	¿M se detiene en w? — Indecidible
HALT es reconocible	Podemos confirmar “sí” pero no “no”
$\overline{\text{HALT}}$ ni reconocible	Ni siquiera podemos enumerar los casos “no”
Rice’s Theorem	Casi toda propiedad no trivial de MTs es indecidible
Reducciones	Técnica para probar nuevos problemas indecidibles

Reflexión Final

El Halting Problem muestra que:

✓ Hay límites fundamentales a lo que podemos computar

✓ Estos límites son matemáticos, no tecnológicos — ninguna computadora futura los superará

✓ La razón es lógica: la auto-referencia crea contradicciones inevitables

Conexión filosófica: Así como Gödel mostró límites en las matemáticas, Turing mostró límites en la computación. Ambos usan ideas similares (diagonalización, auto-referencia).

Siguiente: Gödel y la Conexión →