En la teoría de la computabilidad , el problema de la mortalidad es un problema de decisión que se puede plantear de la siguiente manera:
- Dada una máquina de Turing , decida si se detiene cuando se ejecuta en cualquier configuración (no necesariamente una de inicio)
En la declaración anterior, la configuración es un par , donde q es uno de los estados de la máquina (no necesariamente su estado inicial) yw es una secuencia infinita de símbolos que representan el contenido inicial de la cinta.
,>Tenga en cuenta que, si bien generalmente asumimos que en la configuración inicial todas las celdas de la cinta, excepto un número finito, son espacios en blanco, en el problema de mortalidad, la cinta puede tener un contenido arbitrario, incluidos infinitos símbolos no en blanco escritos en ella.
Philip K. Hooper demostró en 1966 que el problema de la mortalidad es indecidible . Sin embargo, se puede demostrar que el conjunto de máquinas de Turing que son mortales (es decir, se detienen en cada configuración inicial) es recursivamente enumerable .