# Uniform mortality problem for Turing Machines

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.

• Do configurations have to be finite, or do you allow an arbitrary infinite string on the tape? Apr 26, 2019 at 7:08
• 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. Apr 26, 2019 at 8:54

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. 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.

• Why should (1) be true? The finite prefixes of the infinite path are in general witnessed by unrelated configurations. Apr 26, 2019 at 6:56
• 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. Apr 26, 2019 at 6:59
• @EmilJeřábek: $M$ is not mortal (according to the standard definition): consider a configuration in which al tape symbols are $1$. Apr 26, 2019 at 7:05
• I assumed the question was about finite configurations. But anyway, the proof still does not make sense. How do you establish (1)? Apr 26, 2019 at 7:07
• @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}$. Apr 26, 2019 at 7:12