¿Cuál es el resto de 17 al dividir entre 2?
Usa 17=2·8+r.
Tomando q=8 se obtiene 17−16=1, que cumple la restricción del resto.
El resto es 1; por eso el decisor de paridad rechaza 17.
¿El conjunto vacío es decidible? Responde sí/no.
Un algoritmo puede rechazar siempre.
El conjunto vacío no contiene ninguna entrada afirmativa.
Construimos el algoritmo que, para todo natural recibido, responde no y termina inmediatamente.
La respuesta coincide con la pertenencia en todas las entradas; por tanto sí es decidible.
¿La enumerabilidad exige terminar en entradas negativas? Responde sí/no.
Distingue reconocer de decidir.
Una entrada negativa es un natural que no pertenece al conjunto reconocido.
La definición de c.e. exige que no sea aceptada, pero no exige que produzca una respuesta negativa en tiempo finito.
Puede divergir en esa entrada; la respuesta a la pregunta es no.
Explica por qué todo conjunto decidible es enumerable.
Usa el decisor como reconocedor.
Sea D un decisor de A: termina y responde correctamente en cualquier natural.
Para reconocer A ejecutamos D y aceptamos exactamente si D responde sí.
Toda entrada de A acaba aceptada y ninguna ajena es aceptada. Eso basta para que A sea c.e., aunque este reconocedor además termine siempre.
Resume la contradicción diagonal para un supuesto decisor de parada.
Construye un programa que haga lo contrario de la predicción sobre sí mismo.
Suponemos que H(P,x) decide totalmente si el programa P se detiene con entrada x.
Construimos D(P): si H(P,P) responde sí, entra en un bucle; si responde no, termina.
Con P igual al código de D, la respuesta sí predice una parada que D evita; la respuesta no predice una divergencia que D evita. Ambas son imposibles, así que H no existe.