Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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
6  
@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
1  
I think he means finite starting configurations. Right? –  Philip White Feb 15 at 20:34
1  
@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
show 6 more comments

2 Answers 2

up vote 15 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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 Feb 15 at 19:38
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 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 Feb 15 at 20:16
    
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 Feb 15 at 20:27
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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