Given a language that is Turing-Decidable, if you add the empty string to the language then is the new language Turing-Decidable?

I am very confused at this problem because from my understanding the halting states cannot transition to any other state, and in order to accept the empty string your start state would need to be your accept state.

  • $\begingroup$ Is there some reason the start state can’t also be an halt/accept state? $\endgroup$ – amd Nov 3 '15 at 3:23
  • 1
    $\begingroup$ Briefly, No: adding the empty string, or any other finite set of strings, to a language will not change its decidability/undecidability. $\endgroup$ – BrianO Nov 3 '15 at 3:30

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.