3
$\begingroup$

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.

  • 0
    @JDH: Thank I fixed it.2012-08-13

1 Answers 1

10

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

  • 0
    I should have known that the "crazy" one is the same as bounded TM :)2012-08-13