<p>I think there is. We have to make for every L an M that accepts it in such a way that all his moves are recorded on a tape and after every "main step" it checks whether all his steps until that point were really valid. Below I give a sketch about how such a machine should be made (which might contain some minor errors but the main idea should be fine).</p>

<p>Denote a machine that accepts L by T. Now we describe M. First, we copy x to a separate memory tape. Then whenever T would make a move, we write it down on this memory tape, after x. After this, we copy the whole contents of T's tapes into some extra working tapes and check whether from the starting configuration T would really get to its current state after the steps recorded on the memory tape. If not, we halt. If yes, we continue.</p>

CC BY-SA 3.0
2014-02-15T19:38:52.700Z
while writing my answer, I read yours ... which say the opposite :-) ... perhaps I'm wrongly interpreting what is a string accepted by a mortal Turing machine ?
Marzio De Biasi
CC BY-SA 3.0
2014-02-15T20:16:15.717Z
@MarzioDeBiasi: The notion of mortal considered in that paper requires a machine halt in a finite number of steps even if it is started with an infinite amount of arbitrary data on its tape. But I think domotorp's construction at most works for finite configurations. For example, in a configuration with an infinite-length input, domotorp's M gets caught in an infinite sequence of copying the infinite-length input to the separate memory tape...
Joshua Grochow
CC BY-SA 3.0
2014-02-15T20:27:20.687Z
Yes, the difference is that I supposed that every tape content is finite and we know where the boundaries are. Otherwise mortal TM's are just constant, as you write.
domotorp
CC BY-SA 3.0
2014-02-15T19:28:34.217Z
2014-02-15T19:28:34.217Z
domotorp
<p>Here are two results cited in <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.74.6512">Charles E. Hughes "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators"</a>:</p>

<p><strong>Theorem 3</strong>: The class of mortal Turing machines is exactly the class of the constant running time Turing machines.</p>

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

<p>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:</p>

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

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

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

<p><strong>Theorem 4</strong>: the set of mortal Turing machines is recursively enumerable. </p>

CC BY-SA 3.0
2014-02-15T19:36:48.987Z
2014-02-15T19:55:52.537Z
2014-02-15T19:55:52.537Z
Marzio De Biasi
<p>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$)</p>

CC BY-SA 3.0
2014-02-15T17:09:49.823Z
Can you give reference(s) to the Mortal Turing Machines? Thanks :)
Tayfun Pay
CC BY-SA 3.0
2014-02-15T20:17:38.490Z
@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
CC BY-SA 3.0
2014-02-15T20:57:19.187Z
@JoshuaGrochow: I think both options can be interesting, I'm not sure what's the "canonical" definition of mortality.
Marcin Kotowski
CC BY-SA 3.0
2014-02-15T20:58:47.583Z
@Philip: yes, the initial state if the machine can be arbitrary and machine's head can be placed anywhere.
Marcin Kotowski
CC BY-SA 3.0
2014-02-15T21:04:17.770Z
@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
CC BY-SA 3.0
2014-02-15T21:08:17.930Z
@PhilipWhite: as a real world example, think of a device that is processing a stream of data and it can be put on an unknown state/condition because of a hardware failure.
Marzio De Biasi
CC BY-SA 3.0
2014-02-15T21:19:17.873Z
@PhilipWhite: I believe the Hooper paper you cite is the conventional definition, but that you've misinterpreted or misunderstood what is written there. Note that an ID in Hooper's terminology need not be in the *initial* state of TM. And he says a TM is mortal iff each ID (not necessarly those reachable from initial IDs) has a terminal successor. The definition that you are using is very standardly called "total".
Joshua Grochow
<computability>
Is every recursive language recognized by a mortal Turing machine?
Marcin Kotowski
# Is every recursive language recognized by a mortal Turing machine?

(Asked by: username_0 on 2014-02-15)

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$)

**Tags:** computability

> **Comments:**
> **username_1**: Can you give reference(s) to the Mortal Turing Machines? Thanks :)  
> **username_2**: @Marcin: are you interested in machines that halt on all configurations, including infinite ones, or just those that halt on all *finite* configurations?  
> **username_0**: @JoshuaGrochow: I think both options can be interesting, I'm not sure what's the "canonical" definition of mortality.  
> **username_0**: @Philip: yes, the initial state if the machine can be arbitrary and machine's head can be placed anywhere.  
> **username_2**: @Philip: Just imagine the machine in arbitrary state and configuration, and then run the computation forward from that point following the usual rules.  
> **username_3**: @PhilipWhite: as a real world example, think of a device that is processing a stream of data and it can be put on an unknown state/condition because of a hardware failure.  
> **username_2**: @PhilipWhite: I believe the Hooper paper you cite is the conventional definition, but that you've misinterpreted or misunderstood what is written there. Note that an ID in Hooper's terminology need not be in the *initial* state of TM. And he says a TM is mortal iff each ID (not necessarly those reachable from initial IDs) has a terminal successor. The definition that you are using is very standardly called "total".  

---

## 2 answers

### Answer by username_3 on 2014-02-15. Score: 14 | Accepted answer

Here are two results cited in [Charles E. Hughes "Undecidability of finite convergence for concatenation, insertion and bounded shuffle operators"](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.74.6512):

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


---

### Answer by username_4 on 2014-02-15. Score: 9

I think there is. We have to make for every L an M that accepts it in such a way that all his moves are recorded on a tape and after every "main step" it checks whether all his steps until that point were really valid. Below I give a sketch about how such a machine should be made (which might contain some minor errors but the main idea should be fine).

Denote a machine that accepts L by T. Now we describe M. First, we copy x to a separate memory tape. Then whenever T would make a move, we write it down on this memory tape, after x. After this, we copy the whole contents of T's tapes into some extra working tapes and check whether from the starting configuration T would really get to its current state after the steps recorded on the memory tape. If not, we halt. If yes, we continue.

> **Comments:**
> **username_3**: while writing my answer, I read yours ... which say the opposite :-) ... perhaps I'm wrongly interpreting what is a string accepted by a mortal Turing machine ?  
> **username_2**: @MarzioDeBiasi: The notion of mortal considered in that paper requires a machine halt in a finite number of steps even if it is started with an infinite amount of arbitrary data on its tape. But I think username_4's construction at most works for finite configurations. For example, in a configuration with an infinite-length input, username_4's M gets caught in an infinite sequence of copying the infinite-length input to the separate memory tape...  
> **username_4**: Yes, the difference is that I supposed that every tape content is finite and we know where the boundaries are. Otherwise mortal TM's are just constant, as you write.  

---

