Computabilidad y Complejidad

Los límites fundamentales de lo que podemos computar y cuán rápido.

Contenido

Introducción — Las tres grandes preguntas
Algoritmos y Máquinas de Turing — El modelo fundamental
Computabilidad vs Decidibilidad — ¿Qué podemos resolver?
Límites: El Halting Problem — ¿Qué NO podemos resolver?
Gödel y la Conexión — Límites lógicos y computacionales
Complejidad y Big-O — ¿Cuán rápido?
Clases: P, NP y BPP — Jerarquía de dificultad
Síntesis Final — El mapa completo

Preguntas Centrales

Este módulo responde tres preguntas fundamentales sobre la computación:

1. ¿Qué podemos computar?

Respuesta: Todo lo que una Máquina de Turing puede hacer (Church-Turing Thesis)

2. ¿Qué NO podemos computar?

Respuesta: Hay problemas indecidibles (ej: Halting Problem) e incluso no computables

3. ¿Qué tan rápido podemos computar?

Respuesta: Depende de la clase de complejidad (P, NP, etc.)

Conexiones

Este módulo conecta con:

Lógica — Teoremas de Gödel usan ideas similares a Halting
SAT (del módulo anterior) — Es NP-completo, conecta computabilidad con complejidad
Agentes — Define los límites de lo que un agente puede hacer o decidir

Roadmap Visual

¿Qué es computable?
        ↓
Máquinas de Turing (modelo)
        ↓
    ┌───────────────────┐
    │                   │
Computabilidad    Decidibilidad
    │                   │
    └─────────┬─────────┘
              ↓
    ¿Hay límites? → Halting Problem
              ↓
    Gödel: límites lógicos también
              ↓
    De "¿se puede?" a "¿cuán rápido?"
              ↓
        Big-O & Complejidad
              ↓
        P, NP, BPP
              ↓
        P vs NP: el problema del millón

Objetivos de Aprendizaje

Al finalizar este módulo, podrás:

✓ Explicar qué es una Máquina de Turing y por qué importa
✓ Distinguir entre computabilidad y decidibilidad
✓ Demostrar que el Halting Problem es indecidible
✓ Conectar los teoremas de Gödel con límites computacionales
✓ Usar notación Big-O para analizar algoritmos
✓ Clasificar problemas en P, NP o NP-completo
✓ Explicar la importancia de P vs NP
✓ Entender que hay límites fundamentales en lo que podemos computar

Siguiente: Introducción →