Problema de la parada

El problema de la parada o problema de la detención para máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing ${\displaystyle M}$ y una palabra ${\displaystyle w}$, determinar si ${\displaystyle M}$ terminará en un número finito de pasos cuando es ejecutada usando ${\displaystyle w}$ como dato de entrada. Alan Turing, en su famoso artículo On Computable Numbers, with an Application to the Entscheidungsproblem (1936), demostró que el problema de la parada de la Máquina de Turing es indecidible (no computable o no recursivo), en el sentido de que ninguna máquina de Turing lo puede resolver.