Sin embargo, muchos problemas indecidibles "famosos" son al menos semidecidibles, y su complemento es indecidible. Un ejemplo sobre todo puede ser el problema de detención y su complemento.
Sin embargo, ¿alguien puede darme un ejemplo en el que tanto un problema como su complemento sean indecidibles y no semidecidibles? Pensé en el lenguaje de diagonalización Ld, pero no me parece que el complemento sea indecidible.
En ese caso, ¿eso significa que una máquina de Turing M puede "perder" algunas cadenas que en su lugar deberían reconocerse, ya que son parte del lenguaje que estamos tratando de identificar?
fuente