halting problem
Alan Turing demostró en 1936 que no puede haber un procedimiento general para todos los posibles pares de entrada-programa que permita decidir si el programa finalmente se detendrá. Una parte clave de la prueba fue la definición matemática de lo que se ha conocido como máquina de Turing. El problema de la detención es indecidible sobre las máquinas de Turing. Es uno de los primeros ejemplos de un problema de decisión.
- computabilitycomputabilidad
- computability theoryteoría de la computabilidad