juanreutter
commented
2 years ago En el entendido de que toda máquina determinista es también no-determinista (por la definición), en estricto rigor cualquier máquina podría servir acá.
Pero el no determinismo nos ahorra trabajo igual. Por ejemplo, para el caso (a), al sumar un 1 a n_v, un problema que tenemos es que no sabemos si n_v termina en 0 o en 1, y el tratamiento de ambos es un poco distinto. Entonces uno podría hacer una máquina que "adivine" si n_v termina en 0 o en 1, y vaya trabajando con esa suposición.
Para (c) es más extremo aún, uno podría "adivinar" los factores p y q que dividen a |u| y de ahí simplemente chequear que pq = u. Para eso, con input w = 1^n (representando al número n), una máquina no determinista podría pasar por la palabra y escribir al final dos strings 1^p y 1 q, separados con un 0, de forma de terminar en la cinta con 1^n 0 1^p 0 1^q. Después de eso, solo hay que llamar a una máquina determinista que verifique que n = pq, esa máquina es mucho más fácil de programar!
IgnaciaJ
Hola! Estuve intentando de hacer la ayudantía 3, sin embargo, me cuesta imaginarme cómo puedo diseñar una máquina no determinista, algún tip para realizar este tipo de ejercicios?? gracias!!