Mortality (computability theory)

<h2 id="additional-models">Additional models</h2>
The problem can naturally be rephrased for any computational model in which there are notions of "configuration" and "transition". A member of the model will be mortal if there is no configuration that leads to an infinite chain of transitions. The mortality problem has been proved undecidable for:

<ul><li><a href="/facts/Semi-Thue_system/guxDtVd7">Semi-Thue systems</a> and <a href="/facts/Markov_algorithm/3WMjt2As">Markov algorithms</a>.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a></li>
<li><a href="/facts/Counter_machine/FBxEgPld">Counter machines</a><a class="footnote-ref" id="fnref:4" href="#fn:4">4</a></li>
<li><a href="/facts/Dynamical_system/782gREl5">Dynamical systems</a> over 
 
 
 
 
 
 
 R
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathbb {R} }^{n}}
 
 or 
 
 
 
 
 
 
 Q
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathbb {Q} }^{n}}
 
 or 
 
 
 
 
 
 
 Z
 
 
 
 n
 
 
 
 
 {\displaystyle {\mathbb {Z} }^{n}}
 
, for 
 
 
 
 n
 ≥
 2
 
 
 {\displaystyle n\geq 2}
 
, where the transition function is piecewise linear<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a><a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> (here, an arbitrary point, e.g., the origin, is selected as a halting state).</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Hooper, P. (1966). "The undecidability of the Turing machine immortality problem". Journal of Symbolic Logic. 31 (2): 219–234. doi:10.2307/2269811. JSTOR 2269811. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Herman, Gabor (1969). "A simple solution of the uniform halting problem". Journal of Symbolic Logic. 34 (4): 639–640. doi:10.2307/2270856. JSTOR 2270856. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Hooper, P. (1966). "The undecidability of the Turing machine immortality problem". Journal of Symbolic Logic. 31 (2): 219–234. doi:10.2307/2269811. JSTOR 2269811. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Kurtz, Stuart A.; Simon, Janos (2007). "The Undecidability of the Generalized Collatz Problem". Theory and Applications of Models of Computation. Lecture Notes in Computer Science. Vol. 4484. pp. 542–553. doi:10.1007/978-3-540-72504-6_49. ISBN 978-3-540-72503-9. {{cite book}}: |journal= ignored (help) <a href="978-3-540-72503-9" target="_blank">978-3-540-72503-9</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Blondel, Vincent D.; Bournez, Olivier; Koiran, Pascal; Papadimitriou, Christos H.; Tsitsiklis, John N. (2001-03-28). "Deciding stability and mortality of piecewise affine dynamical systems" (PDF). Theoretical Computer Science. 255 (1): 687–696. doi:10.1016/S0304-3975(00)00399-6. ISSN 0304-3975. <a href="https://hal-lara.archives-ouvertes.fr/hal-02101802/file/RR1999-05.pdf" target="_blank">https://hal-lara.archives-ouvertes.fr/hal-02101802/file/RR1999-05.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Ben-Amram, Amir M. (2015-01-01). "Mortality of iterated piecewise affine functions over the integers: Decidability and complexity". Computability. 4 (1): 19–56. doi:10.3233/COM-150032. ISSN 2211-3568. <a href="https://content.iospress.com/articles/computability/com032" target="_blank">https://content.iospress.com/articles/computability/com032</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Mortality (computability theory) open-in-new

Mortality (computability theory)