a) ¿Cómo se podría construir un generador de todos los códigos de Máquinas de Turnig sintácticamente correctos?
Para realizar dicho generador, utilizaremos un generador canónico que, empezando por la cadena vacía, vaya creando cadenas con el alfabeto restringido {0,1,B} , es decir, generará 0,1,00,01,10... etc. Luego, dicha cadena, se tendrá que pasar a un autómata reconocedor de MT's (como el que se dibujó en clase a última hora) para que decida si ese código generado pertenece o no a una MT.
Por tanto la solución sería la que indica el dibujo:
La cosa es que hay infinitas máquinas de turing, por tanto por muchos códigos de MT que construyamos, siempre nos quedarán códigos por obtener.
b) Por el mismo motivo que hemos expuesto al final del apartado a), nos decantamos por la opción 2) ya que aunque nos salgan infinitos códigos de máquinas, nunca voy a conseguir tenerlas todas.
No hay comentarios:
Publicar un comentario