Un lenguaje se llama Decidible o Recursivo si hay una máquina de Turing que acepta y se detiene en cada cadena de entrada w. Todo lenguaje decidible es Turing-Aceptable. Un problema de decisión P es decidible si el lenguaje L de todas las instancias sí a P es decidible.
¿A qué te refieres con Decidibilidad?
: capaz de decidirse específicamente: capaz de decidirse siguiendo o no siguiendo los axiomas de un sistema lógico ¿Era la lógica completa…? ¿Y era decidible, en el sentido de que había un método que demostraba la verdad o falsedad de cada afirmación? -
¿Cuál es la diferencia entre decidibilidad e indecidibilidad?
Un problema de decisión es decidible si existe un algoritmo de decisión para ello. De lo contrario es indecidible. Para mostrar que un problema de decisión es decidible es suficiente dar un algoritmo para él.
¿Cómo se calcula la Decidibilidad?
Una lengua es decidible si y sólo si ella y su complemento son reconocibles. Prueba. Si una lengua es decidible, entonces su complemento es decidible (por clausura bajo complementación).
¿Qué es el problema de Decidibilidad?
(definición) Definición: Un problema de decisión que puede resolverse mediante un algoritmo que se detiene en todas las entradas en un número finito de pasos El lenguaje asociado se denomina lenguaje decidible. También conocido como problema totalmente decidible, algorítmicamente solucionable, recursivamente solucionable.
