7
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ Do configurations have to be finite, or do you allow an arbitrary infinite string on the tape? $\endgroup$
    – Emil Jeřábek
    Apr 26, 2019 at 7:08
  • $\begingroup$ 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. $\endgroup$
    – Bartosz Bednarczyk
    Apr 26, 2019 at 8:54

1 Answer 1

Reset to default
6
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.