<p>The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966))</p>

<p>The <em>uniform mortality problem</em> undecidability follows from the following:</p>

<p><strong>Theorem</strong>: A Turing machine is mortal if and only if it is <em>uniformly mortal</em></p>

<p>I found the proof in: Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: <a href="https://doi.org/10.1016/0743-1066(95)00051-K" rel="noreferrer">Undecidable Boundedness Problems for Datalog Programs</a>. J. Log. Program. 25(2): 163-190 (1995)</p>

<p><strong>Proof:</strong> Let <span class="math-container">$\delta_1,...,\delta_n$</span> be the possible transitions of <span class="math-container">$M$</span>. We call a sequence <span class="math-container">$\delta_{i_1},..,\delta_{i_k}$</span> of transitions <em>consistent</em> if it reflects a computation of <span class="math-container">$M$</span>, i.e., if there exists a configuration <span class="math-container">$c = (l,s,r,q)$</span> (<span class="math-container">$l$</span> left tape, <span class="math-container">$s$</span> symbol under head, <span class="math-container">$r$</span> right tape, <span class="math-container">$q$</span> current state) from which <span class="math-container">$M$</span> will execute that sequence.</p>

<p>Now arrange all consistent transition sequences in a (possibly infinite) tree, with the empty sequence at the root and each node extending the sequence at its parent by one transition. This tree is of bounded degree. Also (1) <span class="math-container">$M$</span> is mortal iff there is non infinite path in the tree, and (2) <span class="math-container">$M$</span> is uniformly mortal iff there are no arbitrarily long paths in the tree. By Konig's Lemma (in a tree of bounded degree there is an infinite path if and only if there is a family of paths of unbounded length), these two conditions are equivalent.</p>

CC BY-SA 4.0
2019-04-26T06:56:39.870Z
Why should (1) be true? The finite prefixes of the infinite path are in general witnessed by unrelated configurations.
Emil Jeřábek
CC BY-SA 4.0
2019-04-26T06:59:24.980Z
In fact, here is a simple counter example: let $M$ move to the right until it finds the empty tape symbol, and then it halts. Then $M$ halts from every configuration, but not in bounded time.
Emil Jeřábek
CC BY-SA 4.0
2019-04-26T07:05:22.770Z
@EmilJeřábek: $M$ is not mortal (according to the standard definition): consider a configuration in which al tape symbols are $1$.
Marzio De Biasi
CC BY-SA 4.0
2019-04-26T07:07:09.600Z
I assumed the question was about *finite* configurations. But anyway, the proof still does not make sense. How do you establish (1)?
Emil Jeřábek
CC BY-SA 4.0
2019-04-26T07:12:01.027Z
@EmilJeřábek: nodes are labeled with sequence of transitions of the $M$ (not sequences of configurations), and each sequence of each node can be "extended" form the parent using a consistent pair of "underlying" configurations $c_{parent}, c_{child}$.
Marzio De Biasi
CC BY-SA 4.0
2019-04-26T07:58:10.393Z
What, exactly, do you mean by a “transition”? Since the set of possible transitions needs to be finite (otherwise the root of the tree has infinite number of immediate successors), I assumed you meant a pairs of states, but possibly you meant something else?
Emil Jeřábek
CC BY-SA 4.0
2019-04-26T09:26:37.710Z
Here is a proof that works. The space of infinite configurations is compact. If the machine halts from a given configuration, it only visits a finite part of the tape, thus any extension of that part also halts in the same number of steps. Thus, for each $k$, the set $H_k$ of configurations from which the TM halts in $k$ steps is open. If the TM halts from any configuration, $\{H_k:k\in\omega\}$ is an open cover, which must have a finite subcover. However, the OP has indicated that the question is indeed about finite configurations, not infinite ones, in which case the results is false.
Emil Jeřábek
CC BY-SA 4.0
2019-04-26T10:20:44.270Z
@EmilJerabek At this point I have some doubts, too. I understood it as: if there is a configuration c such that M makes another step using transition $\delta_i$ then append that transition to the root. Then if there is a valid config c' such that M apply transition $\delta_j$, then add $\delta_i \delta_j$ as a child of $\delta_i$. At every node it is required that it exists an initial config. c on which M will apply the WHOLE transitions sequence that labels the node
Marzio De Biasi
CC BY-SA 4.0
2019-04-26T10:22:06.180Z
Oh, I see: while uniform mortality from finite configurations is strictly stronger than mortality from finite configurations, the uniform mortality problems from finite and infinite configurations are equivalent. Thus the problem is indeed undecidable, assuming Hooper's result is for infinite configurations.
Emil Jeřábek
CC BY-SA 4.0
2019-04-26T13:46:31.067Z
I'm sorry but I don't really get it. Can you explain your idea further?
Bartosz Bednarczyk
CC BY-SA 4.0
2019-04-28T06:58:56.960Z
@BartoszBednarczyk Please be specific. Who of us two is your comment directed at, which of the ideas above are you talking about, and which part of it you don’t understand?
Emil Jeřábek
CC BY-SA 4.0
2019-04-28T14:44:55.140Z
I spend some time thinking about the problem and I think that you are right. Thanks!
Bartosz Bednarczyk
CC BY-SA 4.0
2021-10-01T14:42:49.687Z
It is a bit hard to trace in Hooper's paper, but it can be confirmed that he allows for infinite configurations, so his mortality problem is indeed equivalent to uniform halting time on all (finite) configurations. For instance he says in the intro that his problem is essentially (T2) problem of Buchi, which allows infinite configurations, and also at the beginning of Part V he uses an infinite configuration ...0|0|0|0.... He also says that any unbounded search trivially gives an immortal machine, which would be false if all configurations were finite (unbounded search of "blank").
Denis
CC BY-SA 4.0
2019-04-25T23:40:57.337Z
2019-04-26T06:56:38.310Z
2019-04-26T06:56:38.310Z
Marzio De Biasi
<p>Consider the following generalisation of the mortality problem for Turing Machines.</p>

<blockquote>
  <p>Given a Turing Machine <span class="math-container">$M$</span>. Is there a bound <span class="math-container">$k_M$</span> such that starting
  from any configuration <span class="math-container">$c$</span> machine <span class="math-container">$M$</span> stops after at most <span class="math-container">$k_M$</span> steps?</p>
</blockquote>

<p>Is the presented problem (un)decidable? Can you provide any references? </p>

<p>We stress that "configuration" here means any possible configuration, not only the initial one.</p>

CC BY-SA 4.0
2019-04-26T07:08:37.243Z
Do configurations have to be finite, or do you allow an arbitrary infinite string on the tape?
Emil Jeřábek
CC BY-SA 4.0
2019-04-26T08:54:36.953Z
You can assume that configurations are finite (by putting end-of-world marker or sth like this). However, the length of them can be unbounded.
Bartosz Bednarczyk
<computability><turing-machines><decidability><halting-problem><undecidability>
Uniform mortality problem for Turing Machines
Bartosz Bednarczyk
# Uniform mortality problem for Turing Machines

(Asked by: username_0 on 2019-04-25)

Consider the following generalisation of the mortality problem for Turing Machines.

> Given a Turing Machine $M$. Is there a bound $k\_M$ such that starting
> from any configuration $c$ machine $M$ stops after at most $k\_M$ steps?

Is the presented problem (un)decidable? Can you provide any references?

We stress that "configuration" here means any possible configuration, not only the initial one.

**Tags:** computability, turing-machines, decidability, halting-problem, undecidability

> **Comments:**
> **username_1**: Do configurations have to be finite, or do you allow an arbitrary infinite string on the tape?  
> **username_0**: You can assume that configurations are finite (by putting end-of-world marker or sth like this). However, the length of them can be unbounded.  

---

## 1 answers

### Answer by username_2 on 2019-04-25. Score: 6 | Accepted answer

The mortality problem is undecidable (P.K. Hooper, Th eUndecidability of the Turing Machine Immortality Problem (1966))

The *uniform mortality problem* undecidability follows from the following:

**Theorem**: A Turing machine is mortal if and only if it is *uniformly mortal*

I found the proof in: Gerd G. Hillebrand, Paris C. Kanellakis, Harry G. Mairson, Moshe Y. Vardi: [Undecidable Boundedness Problems for Datalog Programs](https://doi.org/10.1016/0743-1066(95)00051-K). J. Log. Program. 25(2): 163-190 (1995)

**Proof:** Let $\delta\_1,...,\delta\_n$ be the possible transitions of $M$. We call a sequence $\delta\_{i\_1},..,\delta\_{i\_k}$ of transitions *consistent* if it reflects a computation of $M$, i.e., if there exists a configuration $c = (l,s,r,q)$ ($l$ left tape, $s$ symbol under head, $r$ right tape, $q$ current state) from which $M$ will execute that sequence.

Now arrange all consistent transition sequences in a (possibly infinite) tree, with the empty sequence at the root and each node extending the sequence at its parent by one transition. This tree is of bounded degree. Also (1) $M$ is mortal iff there is non infinite path in the tree, and (2) $M$ is uniformly mortal iff there are no arbitrarily long paths in the tree. By Konig's Lemma (in a tree of bounded degree there is an infinite path if and only if there is a family of paths of unbounded length), these two conditions are equivalent.

> **Comments:**
> **username_1**: Why should (1) be true? The finite prefixes of the infinite path are in general witnessed by unrelated configurations.  
> **username_1**: In fact, here is a simple counter example: let $M$ move to the right until it finds the empty tape symbol, and then it halts. Then $M$ halts from every configuration, but not in bounded time.  
> **username_2**: @EmilJeřábek: $M$ is not mortal (according to the standard definition): consider a configuration in which al tape symbols are $1$.  
> **username_1**: I assumed the question was about *finite* configurations. But anyway, the proof still does not make sense. How do you establish (1)?  
> **username_2**: @EmilJeřábek: nodes are labeled with sequence of transitions of the $M$ (not sequences of configurations), and each sequence of each node can be "extended" form the parent using a consistent pair of "underlying" configurations $c_{parent}, c_{child}$.  
> **username_1**: What, exactly, do you mean by a “transition”? Since the set of possible transitions needs to be finite (otherwise the root of the tree has infinite number of immediate successors), I assumed you meant a pairs of states, but possibly you meant something else?  
> **username_1**: Here is a proof that works. The space of infinite configurations is compact. If the machine halts from a given configuration, it only visits a finite part of the tape, thus any extension of that part also halts in the same number of steps. Thus, for each $k$, the set $H_k$ of configurations from which the TM halts in $k$ steps is open. If the TM halts from any configuration, $\{H_k:k\in\omega\}$ is an open cover, which must have a finite subcover. However, the OP has indicated that the question is indeed about finite configurations, not infinite ones, in which case the results is false.  
> **username_2**: @EmilJerabek At this point I have some doubts, too. I understood it as: if there is a configuration c such that M makes another step using transition $\delta_i$ then append that transition to the root. Then if there is a valid config c' such that M apply transition $\delta_j$, then add $\delta_i \delta_j$ as a child of $\delta_i$. At every node it is required that it exists an initial config. c on which M will apply the WHOLE transitions sequence that labels the node  
> **username_1**: Oh, I see: while uniform mortality from finite configurations is strictly stronger than mortality from finite configurations, the uniform mortality problems from finite and infinite configurations are equivalent. Thus the problem is indeed undecidable, assuming Hooper's result is for infinite configurations.  
> **username_0**: I'm sorry but I don't really get it. Can you explain your idea further?  
> **username_1**: @BartoszBednarczyk Please be specific. Who of us two is your comment directed at, which of the ideas above are you talking about, and which part of it you don’t understand?  
> **username_0**: I spend some time thinking about the problem and I think that you are right. Thanks!  
> **username_3**: It is a bit hard to trace in Hooper's paper, but it can be confirmed that he allows for infinite configurations, so his mortality problem is indeed equivalent to uniform halting time on all (finite) configurations. For instance he says in the intro that his problem is essentially (T2) problem of Buchi, which allows infinite configurations, and also at the beginning of Part V he uses an infinite configuration ...0|0|0|0.... He also says that any unbounded search trivially gives an immortal machine, which would be false if all configurations were finite (unbounded search of "blank").  

---

