Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Crazy Turing Machine is the same as Turing machine with one stripe , except of the fact that after each ten steps the head jumps back to the beginning of the stripe.

Lunatic Turing Machine is the same as Turing machine with one stripe , except of the fact that after each 10, 100, 1000, ... steps the head jumps back to the beginning of the stripe.

How come that for a crazy Turing machine we can decide the emptiness problem($L(M)= \emptyset$) and for the lunatic one it stays at $co-RE \setminus R $?

I didn't come with any smart conclusion.

share|improve this question
2  
The standard word for the tape of a Turing machine is "tape" rather than "stripe". –  Carl Mummert Aug 13 '12 at 12:45
    
Thanks Carl, I'll keep it in mind for the next time. –  Jozef Aug 13 '12 at 12:56
    
Jozef, I don't really understand your remark at the end about the complexity of the usual emptiness problem. You write RE-co-RE, but this would seem to be empty. I think you mean to suggest that the usual emptiness problem is co-RE (or what I would call co-CE), which it is since the programs accepting a non-empty set are enumerable, as one can try everything and then include a program on the list whenever it is found to accept something. –  JDH Aug 13 '12 at 13:27
    
@JDH: Thank I fixed it. –  Jozef Aug 13 '12 at 13:29

1 Answer 1

up vote 8 down vote accepted

The crazy Turing machine can never get beyond the $10^{th}$ cell of the tape, and has ultimately only finitely many configurations. The complete spectrum of behavior of such a machine is therefore computable by a regular Turing machine, which can build the graph of all configurations and compute which configurations reach others and then find if there is an accepting path through these configurations. In particular, the emptiness problem for the crazy Turing machines will be decidable.

According to my understanding of the lunatic Turing machines, however, they get longer and longer periods of time during which they may perform "normal" computation, and so they can systematically make progress on deciding a semi-decidable question. Whenever the lunatic behaviro sets in, this will be detectable, and the machine can simply return to where it was and continue its calculation further. It was merely interrupted by a small hiccup. So these machines are fully as powerful as regular Turing machines, and so their emptiness problem is co-c.e. (since non-emptiness is verified by an accepting instance).

share|improve this answer
    
Thank you @JDH. –  Jozef Aug 13 '12 at 12:50
    
I should have known that the "crazy" one is the same as bounded TM :) –  Jozef Aug 13 '12 at 12:55

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.