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.