El problema de la parada y P vs NP: Tim Roughgarden explica los límites de la computación
Computation as a Universal and Fundamental Concept
En este curso gratuito, Tim Roughgarden explora una pregunta fundamental: ¿hay algo que las computadoras no puedan hacer? Comienza con el teorema de Turing de 1936 y el problema de la parada, demostrando que existen problemas irresolubles. Luego pasa a la complejidad computacional, presentando atajos algorítmicos como el de Dijkstra y Karatsuba, y cómo el problema del viajante lleva a la teoría de NP-completitud. Concluye con P vs NP, el problema abierto más importante en ciencias de la computación, y sus implicaciones para la criptografía, la IA y la computación cuántica.
El problema de la parada, que pregunta si un programa eventualmente se detendrá, está para siempre fuera del alcance de cualquier computadora.