# Is every recursive language recognized by a mortal Turing machine?

We say that a Turing Machine $M$ is mortal if $M$ halts for every starting configuration (in particular, the tape content and initial state can be arbitrary). Is every recursive language recognized by a mortal Turing Machine? (i.e. if there is a TM that accepts $L$, there is also mortal TM that accepts $L$)

-
Can you give reference(s) to the Mortal Turing Machines? Thanks :) –  Tayfun Pay Feb 15 at 17:09
How is it that the initial state can be arbitrary? Isn't a mortal Turing machine just a TM that halts on every input? –  Philip White Feb 15 at 20:12
@Marcin: are you interested in machines that halt on all configurations, including infinite ones, or just those that halt on all finite configurations? –  Joshua Grochow Feb 15 at 20:17
I think he means finite starting configurations. Right? –  Philip White Feb 15 at 20:34
@Philip: Just imagine the machine in arbitrary state and configuration, and then run the computation forward from that point following the usual rules. –  Joshua Grochow Feb 15 at 21:04

Here are two results cited in Charles E. Hughes "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators":

Theorem 3: The class of mortal Turing machines is exactly the class of the constant running time Turing machines.

$ConstT = \{ M \mid \exists s$ s.t. for all initial configurations $C$, $M$ halts in no more than $s$ steps $\}$

So I think that we can derive the following: given a mortal Turing machine $M$, let $M', s$ be the corresponding constant time TM and its running time. The language recognized by $M$ over alphabet $\Sigma = \{0,1\}$ is exactly:

$$\{ xy \mid |x| \leq s \land M' \text{ accepts } x \text{ in no more than s steps}, y \in \{0,1\}^* \}$$

So the class of languages recognized by mortal Turing machines is a proper subset of the class of regular languages. For example you can use $L = \{(0|1)^*1^*\}$ to fool every constant time TM.

Things get interesting when we try to decide if a Turing machine is mortal because we have to face with arbitrary (finite) initial tape and state.

Theorem 4: the set of mortal Turing machines is recursively enumerable.

-