Что вы делаете, когда доказываете, что язык решаем?

Question

Что вы делаете, когда доказываете, что язык решаем?

Answer 1

Если вы спросите, КАК это сделано, я не уверен, но я могу проверить.

По сути, decidable - это язык, для которого можно построить алгоритм (т. Е. Машину Тьюринга), который остановит ЛЮБОЙ конечный ввод (с принятием или отклонением ввода). Неразрешимый - это язык, который нельзя решить.

http://en.wikipedia.org/wiki/Recursive_language... но больше по теме можно легко найти. По этой ссылке есть только краткое упоминание этого термина.

ps Итак, при построении вышеупомянутого алгоритма вы в основном доказываете, что язык разрешим.