REC (Turing decidable) :
- A language is REC if there exists a TM that
accepts all those strings that ∈ language
rejects all those strings that ∉ language
by accept we mean that TM would halt in Final state.
by reject we mean that TM would halt in Non-final state.
In other words Any language for which you can write a program and get a positive or negative reply from your computer , i.e technically speaking , you can design a TM and ensures that it always accepts or rejects. Then this language is REC.
2. As for REC languages TM would always 'halt' so in another words we can say if some problem is solvable by computer (mean algo exists) then this language is REC.
RE(Turing recognizable / Semidecidable):
A language is RE iff any
w ∈ lang => TM halts in a Final state.
w∉ lang => TM halts in Non-final state or loops forever(hang).
in another words If there exists a TM that accepts every string that ∈ lang and doesn't accept strings that are not in the language (Strings that are not in languauge may be rejected or may cause the TM to go into an infinite loop).
Hope you know every REC is RE but vice-versa is not true.