Recognizable vs Decidable
A language is Recognizable iff there is a Turing Machine which will halt and accept only the strings in that language and for strings not in the language, the TM either rejects, or does not halt at all. Note: there is no requirement that the Turing Machine should halt for strings not in the language.
A language is Decidable iff there is a Turing Machine which will accept strings in the language and reject strings not in the language.
Perhaps this link will be helpful: http://kilby.stanford.edu/~rvg/154/handouts/decidability.html
Disclaimer : I'll elaborate just a little.
When a Turing Machine(TM) is given an input, it can do one of three things :
- Accept the input by reaching accept state ($q_{accept}$).
- Reject the input by reaching reject state ($q_{reject}$).
- Keep computing forever. This can be called a "loop".
If the machine keeps computing forever, we consider that the machine has rejected the string but it does so in an infinite number of steps. Thus, if the machine accepts a string, it must do so in a finite number of steps!
A Language of a Turing Machine is simply the set of all strings that are accepted by the Turing Machine. In this case, we say that the Language is recognized by the Turing Machine. This brings me to the definition of a Turing Recognizable Language :
Def : A Language is called Turing Recognizable if some Turing Machine recognizes it.
Now, consider a Turing Machine $M$ and a language $L$(over input alphabet $\Sigma$) that is recognized by $M$. Thus, $L$ is a Turing Recognizable Language (since the TM $M$ recognizes it). Consider the set of strings that are not in $L$(we call it $\overline{L}$). We know that the machine $M$ does not accept these strings. So, when we simulate a string $w$ $\in$ $\overline{L}$ on $M$, there are two possibilities :
- M ends up on reject state ($q_{reject}$).
- M keeps computing forever(goes in a "loop").
If the machine $M$ is such that for all $w$ $\in$ $\overline{L}$, it produces the output by going into the reject state, then we have a Turing Machine($M$) for $L$ which has the property that, for any input (over $\Sigma^{*}$) it never goes into a loop! Thus, we can say that for any input (over $\Sigma^{*}$), the Turing Machine $M$ decides whether to accept or reject the input in a finite number of steps. The machine $M$ is called a decider. The languages for which we can design Turing Machines with the above property are called Turing Decidable languages. In the above example, we say that $M$ decides $L$. Here is the definition :
Def : A Language is called Turing Decidable if some Turing Machine decides it.
Keeping it simple - A language $L$ is Turing Decidable if some decider $M$, decides it.
For more information you can refer to : An Introduction to the Theory of Computation by Michael Sipser.
My answer mostly agrees with Aryabhata’s:
A language is “Turing-Recognizable” iff there exists a Turing Machine such that
when encountering a string in that language, the machine terminates and accepts that string;
when encountering a string not in that language, the machine either terminates and rejects that string or doesn’t terminate at all.
A language is “Turing-Decidable” iff there exists a Turing Machine such that
when encountering a string in that language, the machine terminates and accepts that string;
when encountering a string not in that language, the machine terminates and rejects that string.
Note that “Turing-Decidable” is a stronger condition than “Turing-Recognizable”, because, if a language is Turing-Decidable then its corresponding Turing Machine never runs forever.