¿Cuál de los siguientes es/son indecidibles?
(A)
Dadas dos máquinas de Turing M1 y M2, decida si L(M1) = L(M2).
(B)
Dada una máquina de Turing M, decide si L(M) es regular.
(C)
Dada una máquina de Turing M, decida si M acepta todas las strings.
(D)
Dada una máquina de Turing M, decide si M da más de 1073 pasos en cada cuerda.
Respuesta: (A) (B) (C)
Explicación:
Opción A: Es indecidible comprobar la equivalencia de 2 RELs.
Opción B: es una propiedad no trivial de los REL, por lo tanto, es indecidible .
Opción C: también es una propiedad no trivial de los REL, por lo que es indecidible .
Opción D: si TM ejecuta al menos 1073 pasos en todas las entradas de longitud hasta 1073, se comportará igual en todas las entradas de todas las longitudes y, por lo tanto, ejecutará al menos 1073 pasos en todas las entradas. Por lo tanto, es decidible.
Cuestionario de esta pregunta
Comente a continuación si encuentra algo incorrecto en la publicación anterior
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