Если вы спросите, КАК это сделано, я не уверен, но я могу проверить.
По сути, decidable - это язык, для которого можно построить алгоритм (т.е. машину Тьюринга), который остановит ЛЮБОЙ конечный ввод (с принятием или отклонением ввода).
Неразрешимый - это язык, который нельзя решить.
http://en.wikipedia.org/wiki/Recursive_language ... но больше по теме можно легко найти. По этой ссылке есть только краткое упоминание термина.
p.s. Итак, при построении вышеупомянутого алгоритма вы в основном доказываете, что язык разрешим.