Theoretical Computer Science

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

## Solution

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.

• +0 – 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 06:59
• +0 – @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 07:05
• +0 – @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 07:12