Search code examples
computer-scienceregular-languagecomputation-theoryturing-machines

Does there exist a regular language that's not Turing Recognizable?

Is it possible for a regular language to be non-Turing Recognizable?

Solution

  • Nope! If you have a regular language, you can get a DFA for it, then convert that DFA into a Turing machine by slightly adjusting the transitions so that they mechanically move the tape head forward. As a result, that language is also Turing-recognizable.