EJERCICIO 1 / 5Respuesta comprobable
Tu reto 1.
Número mínimo de estados del autómata de paridad de unos descrito.
- PISTA 1
Una pista
Debe distinguir par e impar.
Un desarrollo posible.
Los prefijos vacíos y1 requieren respuestas distintas si la entrada termina inmediatamente: uno tiene paridad par y otro impar.
Un autómata determinista que los confundiera en un estado daría la misma respuesta y fallaría en uno.
Por ello se necesitan al menos2 estados; la construcción con P e I muestra que2 bastan.
EJERCICIO 2 / 5Respuesta comprobable
Tu reto 2.
Número de cadenas binarias de longitud cuatro.
- PISTA 1
Una pista
Dos elecciones por posición.
Un desarrollo posible.
Cada una de las cuatro posiciones tiene dos opciones,0 o1.
Las cadenas distinguen posiciones y permiten repeticiones y ceros iniciales.
El producto2·2·2·2=16 cuenta todas las cadenas de longitud4.
EJERCICIO 3 / 5Respuesta comprobable
Tu reto 3.
Número de unos en la cadena 10101.
- PISTA 1
Una pista
Cuenta las apariciones.
Un desarrollo posible.
En10101, los símbolos de las posiciones1,3 y5 son unos.
Hay tres apariciones en total.
Como3 es impar, el autómata de paridad terminaría en I.
EJERCICIO 4 / 5Razonamiento · revisión personal
Tu reto 4.
Resume la contradicción del problema de parada.
- PISTA 1
Una pista
Haz que un programa actúe al revés de la predicción sobre sí mismo.
Un desarrollo posible.
Supongamos un decisor H que termina y decide la parada para cualquier pareja programa-entrada.
Construimos D(p): si H(p,p) predice parada, entra en bucle; si predice no parada, termina.
Ejecutamos D con su propio código.
Si H predice parada, D no termina; si predice no parada, termina. Ambas alternativas contradicen H, que no puede existir.
EJERCICIO 5 / 5Razonamiento · revisión personal
Tu reto 5.
¿Indecidible significa que ninguna entrada concreta pueda resolverse?
- PISTA 1
Una pista
Distingue caso individual y algoritmo universal.
Un desarrollo posible.
Indecidibilidad se refiere a la inexistencia de un procedimiento universal que termine correctamente en todas las entradas.
Por ejemplo, se puede demostrar que un programa sin bucles termina o que otro tiene un bucle incondicional.
Resolver esos casos concretos es compatible con que no exista un decisor general de parada.
Incluso clases completas restringidas pueden ser decidibles; el dominio de la afirmación debe conservarse.