Cuando están demostrando una lengua es decidible, ¿qué haces con eficacia?

Question

Cuando están demostrando una lengua es decidible, ¿qué haces con eficacia?

Answer 1

Si preguntando ¿cómo se hace, estoy seguro, pero puedo comprobar.

Básicamente, decidable es el idioma para el que se puede construir un algoritmo (es decir, máquina de Turing) que detener para cualquier entrada finita (con aceptar o rechazar la entrada). Indecidible es el idioma que no es decidible.

http://en.wikipedia.org/wiki/Recursive_language ... pero más sobre el tema se pueden encontrar fácilmente. En este enlace hay sólo una rápida mención del término.

p.s. Por lo tanto, cuando se construye por encima de algoritmo antes mencionado, que son básicamente demostrando que el lenguaje es decidible.