Úmrtnost (teorie vypočítatelnosti) - Mortality (computability theory)

v teorie vypočítatelnosti, úmrtnost problém je rozhodovací problém což lze konstatovat následovně:

Vzhledem k Turingův stroj, rozhodnout, zda se zastaví při spuštění jakékoli konfigurace (ne nutně počáteční)

Ve výše uvedeném prohlášení je konfigurace dvojice , kde q je jeden ze stavů stroje (nemusí to nutně být jeho počáteční stav) a w je nekonečná posloupnost symbolů představujících počáteční obsah pásky. Všimněte si, že i když obvykle předpokládáme, že ve výchozí konfiguraci je až na konečně mnoho buněk na pásce prázdných, v problému úmrtnosti může mít páska libovolný obsah, včetně nekonečně mnoha napsaných neprázdných symbolů.

Philip K. Hooper v roce 1966 prokázal, že problém úmrtnosti je nerozhodnutelný. Je však možné ukázat, že sada Turingových strojů, které jsou smrtelné (tj. Zastaví se při každé počáteční konfiguraci), je rekurzivně spočetné.