¿Cuál de los siguientes problemas es decidible?
- I. Dado un TM M y una string y, ¿M alguna vez escribe el símbolo # en su cinta en la entrada y?
- II. Dada una gramática libre de contexto G sobre {a, b}, ¿G genera todas las strings del lenguaje {a, b} * de longitud ≤ 381?
- tercero Dado un TM M, ¿existen infinitos TM M’aceptando el mismo conjunto recursivo enumerable A = L(M)?
- IV. Dada una TM M y una string y, ¿M acepta y?
(A) I y II
(B) II y III
(C) I, II y III
(D) II y IV
Respuesta: (B)
Explicación:
- I. Indecidible, ya que a él se reduce el problema de la detención. De hecho, dado M (sin # entre el alfabeto de la cinta) construye M′ de la siguiente manera: M′simula M pero cada vez que M quiere detenerse, M′primero imprime # y luego se detiene. Está claro que M en y si y sólo si M’ escribe ]en la entrada y. Por lo tanto, si pudiéramos decidir (a) podríamos decidir el problema de detención.
- II. Decidible: cada problema individual x ∈ L(G ) es decidible, y tenemos que comprobar si cada string de longitud ≤ 381 (un conjunto finito dado de ellas) está en L(G).
- tercero decidible. Esta es una propiedad trivial, ya que para cada TM M hay infinitos TM M′ que aceptan el mismo reinicio A = L(M).
- IV. Indecidible. De lo contrario, podríamos decidir el problema ‘¿es M acepta ε?’. Este último es indecidible por el Teorema de Rice, ya que corresponde a una propiedad no trivial de los re conjuntos ε ∈ L(M).
Entonces, la opción (B) es correcta.
Cuestionario de esta pregunta
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