1
$\begingroup$

Consider the language L = {: M is a TM and M visits its start state at least twice when executed on ε}. Prove L with respect to decidability, recognizability, and co-recognizability.

I think the problem is recognizable, but not co-recognizable. I am trying to reduce the problem to halting problem in order to prove this. I am not sure how to create a Turing Machine for the reduction.

$\endgroup$
  • $\begingroup$ What have you tried so far? $\endgroup$ – Mohammad Zuhair Khan Apr 30 at 16:55
  • $\begingroup$ I think the problem is recognizable, but not co-recognizable. I am trying to reduce the problem to halting problem in order to prove this. I am stuck at this part. $\endgroup$ – Ozzy Dozzy Apr 30 at 17:12
  • $\begingroup$ I suggest you add that information to the question body as it details what you have attempted and provides more context. $\endgroup$ – Mohammad Zuhair Khan Apr 30 at 17:15
  • $\begingroup$ I have edited the post $\endgroup$ – Ozzy Dozzy Apr 30 at 17:17
  • $\begingroup$ @MohammadZuhairKhan Do you happen to know how to approach this? $\endgroup$ – Ozzy Dozzy Apr 30 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.