Śmiertelność (teoria obliczalności)

W teorii obliczalności problem śmiertelności jest problemem decyzyjnym , który można sformułować w następujący sposób:

Biorąc pod uwagę maszynę Turinga , zdecyduj, czy zatrzymuje się ona po uruchomieniu w dowolnej konfiguracji (niekoniecznie początkowej)

W powyższym stwierdzeniu konfiguracja to para , gdzie q to jeden ze stanów maszyny (niekoniecznie jej stan początkowy), aw to nieskończona sekwencja symboli reprezentujących początkową zawartość taśmy. Zauważ, że podczas gdy zwykle zakładamy, że w początkowej konfiguracji prawie wszystkie komórki na taśmie są puste, w przypadku problemu śmiertelności taśma może mieć dowolną zawartość, w tym nieskończenie wiele zapisanych na niej niepustych symboli.

Philip K. Hooper udowodnił w 1966 r., że problem śmiertelności jest nierozstrzygalny . Można jednak wykazać, że zbiór maszyn Turinga, które są śmiertelne (tzn. zatrzymują się na każdej początkowej konfiguracji) jest przeliczalny rekurencyjnie .