Turning Machine - Recursively Enumerable Language

As we learnt in the previous articles, a Turning Machine may

  • either accept the input or halt
  • either reject the input or halt
  • never halt or continue

A recursively enumerable language is the language which accepts every string otherwise not. If a language halt on every string, it is called a recursive language.

The recursive enumerable language is generated by Unrestricted Grammar or type-0 language.

A language L is a recursive enumerable language and M is a Turning machine that accepts the input string w :

If w ∈ L, M halts for the final state
if w ∉ L, M halts in a non-final state, loop forever.