[seanwilson]

A simple summary is: a problem domain is decidable if there exists an algorithm that will always be able to tell you true or false if any problem in that domain is solvable.

Some examples of this are propositional logic and linear logic are decidable, whereas the halting problem and nonlinear logic are not.

For instance, the halting problem isn't decidable because although you can answer true or false for some specific programs, there exists programs where you do not know if they halt or not. Arbitrary mathematical problems in general are undecidable (see Gödel's incompleteness theorems) but we can still carve out domains within this that are decidable.

[eru]

To be pedantic: the Halting Problem for Turing Machines is undecidable. There are simpler computing models for which we can decide halting.