Desarrollo de las ciencias computacionales
miércoles 12 de agosto · 16:00–17:15 · hace 10 días
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.