Question

Consider the language L-1(M): M is a TM and M visits its start state at least twice when executed on ε} Completely classify L with respect to decidability, recognizability, and co-recognizability.

Answer 1

L belongs to recognizable class because for input $\epsilon$, if M visit twice then it can be recognized by a TM but it is not decidable.

Consider the reduction of input <M,w> of halting problem into input <M1> of L as follows :-

1. Given input <M,w> , create TM M1, which have a new starting state q' and on input $\epsilon$, M1 writes w on tape input tape and move to start of the tape header with the state being q0, which is the initial state of M.

2. Now M1 with tape containing w will behave exactly like M.

3. If M1 reaches any halting configuration , it makes transition to its starting state q'.

Now M1 will reenters it's starting state second time only if M halts on w. Which means M1 belongs to L if <M,w> belongs to halting instance, which is undecidable and hence L is also undecidable .

Please comment for any clarification.