GUÍA 12-08-26 Teoría de la Computación

NE111 · miércoles 12/08/2026 · 16:00-17:15 · Sesión 2

Desarrollo de las ciencias computacionales

POR QUÉ VER LA HISTORIA

Los modelos formales del curso no salieron de la nada: son respuestas a preguntas concretas que alguien se hizo. Entender la pregunta hace que el modelo deje de parecer arbitrario.

ANTES DE QUE HUBIERA COMPUTADORAS

• Siglo XIX — Babbage diseña la máquina analítica; Ada Lovelace escribe lo que se reconoce como el primer algoritmo destinado a una máquina.
• Boole formaliza la lógica como álgebra, lo que después permitirá construir circuitos digitales.

LA CRISIS DE LOS FUNDAMENTOS

A inicios del siglo XX, Hilbert plantea su programa: encontrar un procedimiento mecánico que decida la verdad de cualquier enunciado matemático. Era el Entscheidungsproblem, el problema de la decisión.

La respuesta llegó en negativo y de tres lados a la vez.

• 1931 — Gödel demuestra sus teoremas de incompletitud: todo sistema formal suficientemente potente tiene enunciados verdaderos que no puede demostrar.
• 1936 — Church formula el cálculo lambda y demuestra que el problema de la decisión no tiene solución.
• 1936 — Turing, de forma independiente, define su máquina abstracta y llega al mismo resultado.

POR QUÉ GANÓ EL MODELO DE TURING

El cálculo lambda de Church y las funciones recursivas de Gödel y Kleene son igual de potentes, pero la máquina de Turing es la que se parece a algo mecánico. Se puede imaginar, dibujar y explicar sin formación en lógica, y por eso es la que se volvió el modelo de referencia.

DE LA TEORÍA A LA MÁQUINA FÍSICA

• 1937 — Shannon muestra que el álgebra de Boole describe circuitos de conmutación.
• 1945 — Von Neumann describe la arquitectura de programa almacenado.
• 1940s — ENIAC, Colossus y las primeras máquinas electrónicas.

Fíjate en el orden: la teoría de la computabilidad es anterior a la primera computadora electrónica. Turing demostró qué no podría hacer una computadora antes de que existiera una.

LA SEGUNDA OLA: EFICIENCIA

Resuelto qué es computable, la pregunta se desplazó a cuánto cuesta. En 1971 Cook formula el problema P contra NP, que sigue abierto y es uno de los siete problemas del milenio.

LO QUE SIGUE

La próxima sesión define con precisión qué es un algoritmo y presenta las tres áreas en que se divide el curso.