Tugurium/GTI

Glosario Terminología Informática

halting problem

0 problema de la parada, problema de la detención
Problema de decisión en la teoría de la computabilidad que intenta determinar, a partir de la descripción de un programa arbitrario y una entrada, si el programa terminará de ejecutarse o continuará funcionando para siempre.
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.
2018-02-15