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.


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.

Comments (5)

  • +0 – Why should (1) be true? The finite prefixes of the infinite path are in general witnessed by unrelated configurations. — Apr 26, 2019 at 06:56  
  • +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 – 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 07:07  
  • +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  

External Links

External links referenced by this document: