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$)
$\begingroup$
$\endgroup$
11
-
1$\begingroup$ Can you give reference(s) to the Mortal Turing Machines? Thanks :) $\endgroup$– Tayfun PayCommented Feb 15, 2014 at 17:09
-
$\begingroup$ How is it that the initial state can be arbitrary? Isn't a mortal Turing machine just a TM that halts on every input? $\endgroup$– user1338Commented Feb 15, 2014 at 20:12
-
6$\begingroup$ @Marcin: are you interested in machines that halt on all configurations, including infinite ones, or just those that halt on all finite configurations? $\endgroup$– Joshua GrochowCommented Feb 15, 2014 at 20:17
-
1$\begingroup$ I think he means finite starting configurations. Right? $\endgroup$– user1338Commented Feb 15, 2014 at 20:34
-
1$\begingroup$ @Philip: Just imagine the machine in arbitrary state and configuration, and then run the computation forward from that point following the usual rules. $\endgroup$– Joshua GrochowCommented Feb 15, 2014 at 21:04
|
Show 6 more comments
2 Answers
$\begingroup$
$\endgroup$
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.
answered Feb 15, 2014 at 19:36
$\begingroup$
$\endgroup$
3
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.
-
$\begingroup$ 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 ? $\endgroup$ Commented Feb 15, 2014 at 19:38
-
2$\begingroup$ @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... $\endgroup$ Commented Feb 15, 2014 at 20:16
-
$\begingroup$ 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. $\endgroup$– domotorpCommented Feb 15, 2014 at 20:27