Mortalidade (teoria da computabilidade)

Na teoria da computabilidade, o problema da mortalidade é um problema de decisão que pode ser enunciado como segue:

Dada uma máquina de Turing, decidir se pára quando executada em uma configuração qualquer (não necessariamente uma configuração inicial)

Na declaração acima, a configuração é um par <q, w>, onde q é um dos estados da máquina (não necessariamente seu estado inicial) e w é uma sequência infinita de símbolos que representam o conteúdo inicial da fita. Note-se que enquanto geralmente assumimos que na configuração inicial quase todo número finito de células na fita são espaços em branco, no problema da mortalidade a fita pode ter conteúdo arbitrário, incluindo um número infinito de símbolos que não estão com o símbolo "em branco" escrito nela.

Philip K. Hooper provou em 1966 que o problema da mortalidade é indecidível. No entanto, pode-se mostrar que o conjunto de máquinas de Turing que são mortais (ou seja, que param em todas as configurações iniciais) é recursivamente enumerável.