Semidécidables

Semidécidables es un término de la teoría de la computabilidad que describe un conjunto de cadenas (un lenguaje) para el cual existe una máquina de Turing que, al recibir una entrada x, se detiene y acepta si x pertenece al lenguaje, y puede no detenerse si x no pertenece. En otras palabras, es posible verificar la pertenencia, pero no necesariamente negar la pertenencia.

Una caracterización clave es que los lenguajes semidecidibles son exactamente los lenguajes recursivamente enumerables (RE). Esto significa que existe un procedimiento que lista todos los elementos del lenguaje, o bien una función parcial computable que, aplicada a una entrada, devuelve una respuesta positiva cuando la entrada pertenece y no devuelve nada cuando no pertenece. En cualquiera de los casos, las entradas que pertenecen al lenguaje pueden ser aceptadas por una máquina, aunque la máquina pueda quedarse sin detenerse para las demás.

Relación con la decidibilidad: un lenguaje es decidible si hay una máquina que se detiene en todos los casos y acepta o rechaza según si la entrada pertenece o no al lenguaje. Un lenguaje semidécidible puede no ser decidible, y las clases RE no son cerradas bajo complemento. En particular, HALT (el problema de detención) es semidécidible pero indecidible; su complemento no es semidécidible.

Ejemplos y uso: el conjunto de entradas que describen programas que se detienen en una entrada dada es semidécidable; existen lenguajes semidecidibles que no son decidibles, y muchos problemas de teoría de la computación se estudian dentro de esta clase.