[Tarea 3] Duda respecto al no-determinismo

[lewebe]

Hola, en el caso de una maquina no-deterministica a la cual se le presenten dos o más posibles configuraciones para elegir, asumimos que la que elige es al azar? O que hay un "oráculo" que le dice cual configuración elegir (como lo vimos en clase)?

[lewebe]

Dicho de otra manera, me basta demostrar que alguna de las hojas de mi árbol de configuraciones llega a un estado de aceptación para demostrar que mi máquina no determinista acepta el lenguaje en cuestión? O debo construir mi máquina tal que asegure que siempre "elegirá" las configuraciones correctas para llegar a ese estado de aceptación si es que lo hay y el input es correcto?

[juanreutter]

Es un poco extraña la pregunta, por que la leo como "usamos lo que vimos en clase u otra cosa"... no entiendo por que les podría pasar un concepto en clases y después pedir otro en la tarea (jaja, uno es desorganizado pero no tanto).

Las máquinas están en los apuntes, en las clases, la semántica está ahí también! tiene que ser una hoja de las configuraciones la que acepte.

[lewebe]

ok, perdón por la pregunta obvia jajaja :( no había hecho la conexión y pensé que tenía que asegurar que mi máquina siempre llegue al estado de aceptación si es que lo hay.

[juanreutter]

Esa semantixa que tu dices tambien existe! No lo he pensado, pero deberiamos poder demostrar que una maquina de turing no determinista bajo la semantica de "todos los estados aceptan" acepta los lenguajes coRE