Aprendimos sobre el concepto de enumeraciones de funciones. En la práctica, corresponden a lenguajes de programación. En un comentario pasajero, el profesor mencionó que la clase de todas las funciones totales (es decir, las funciones que siempre terminan para cada entrada) no es enumerable. Eso...
Un conjunto es contable si tiene una biyección con los números naturales, y es computablemente enumerable (ce) si existe un algoritmo que enumera sus miembros. Cualquier conjunto enumerable computable no finito debe ser contable ya que podemos construir una biyección a partir de la...
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...