RE or REL(recursive enumerable languages) or Turing-recognizable are same.
recursive or decider or Turing-decider are same .
when we start a Turing machine on an input, three outcomes are possible. That the Turing machine may ---
- Accept the input
- Reject the input
- Loop (by loop mean that the machine simply does not halt. Looping may entail any simple or complex behavior that never leads to a halting state.)
RECURSIVE LANGUAGE:
when a Turing machine halts on all inputs (i.e. Accept or Reject the inputs) , never loops , such Turing machines are called decider or Turing-decider. And that language is called recursive or Turing decidable
RECURSIVE ENUMERABLE LANGUAGE:
when a Turing machine may halt(i.e. Accept or Reject the inputs) or may not halt (means Turing machine go into loop), such Turing machines are called Turing-recognizer. And that language is called recursive-enumerable or Turing-recognizable.
* But sometimes it is difficult to distinguish that a Turing machine is looping or taking a long time for an input.(i.e. UNDECIDABILITY)
* Every recursive language is recursive enumerable.
in other words,
a language L is said to be decidable if L is Turing-recognizable and L' is also Turing-recognizable.