Supongamos que M1 y M2 son dos TM tales que L(M1) = L(M2). Después
(A) En cada entrada en la que M1 no se detiene, M2 tampoco se detiene.
(B) En cada i/p en el que M1 se detiene, M2 también se detiene.
(C) En cada i/p que M1 acepta, M2 se detiene.
(D) Ninguna de las anteriores.
Respuesta: (C)
Explicación:
M2 acepta strings en L(M1) por lo que definitivamente se detendrá. Otros 2 no están garantizados, ya que la máquina de Turing M no acepta w si rechaza w deteniéndose en un estado de rechazo o realiza un bucle infinito en w.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA