– Se dice que un problema de decisión P es semidecidible (es decir, tiene un semialgoritmo) si el lenguaje L de todas las instancias sí a P es r.e. – (Problema de equivalencia para DFA) Dados dos DFA, ¿aceptan el mismo idioma? Prueba: recuerda el argumento de Cantor de la primera conferencia.
¿Cuándo se dice que un problema es semidecidible?
Los problemas semidecidibles son aquellos en los que una máquina de Turing se detiene en la entrada aceptada por ella, pero puede detenerse o repetirse para siempre en la entrada rechazada por la máquina de Turing. Estos problemas se denominan problemas reconocibles de Turing.
¿Qué es un problema parcialmente decidible?
Definición: Uno cuyo lenguaje asociado es un lenguaje recursivamente enumerable. De manera equivalente, existe un algoritmo que se detiene y genera 1 para cada instancia que tiene una respuesta "sí", pero para las instancias que tienen una respuesta "no" se permite no detenerse o detenerse y generar 0.
¿El problema de la detención es parcialmente decidible?
Alan Turing demostró en 1936 que no necesariamente puede existir un algoritmo general que se ejecute en una máquina de Turing y que resuelva el problema de detención para todos los pares de entrada de programa posibles. Por lo tanto, el problema de detención es indecidible para las máquinas de Turing.
¿Por qué el problema de la detención es semidecidible?
Se dice que un idioma es semidecidible si existe una máquina de Turing que se detiene si una palabra pertenece al idioma (casos SÍ) y puede rechazar o entrar en infinito bucle si la palabra no pertenece al idioma (SIN mayúsculas y minúsculas).
