¿Cuáles de los siguientes lenguajes son indecidibles? Tenga en cuenta que ⟨M⟩ indica la codificación de la máquina de Turing M.
- L 1 = { ⟨M⟩ ∣ L(M)=∅ }
- L 2 = { ⟨M,w,q⟩ ∣ M en la entrada w alcanza el estado q en exactamente 100 pasos }
- L 3 = { ⟨M⟩ ∣ L(M) no es recursivo }
- L 4 = { ⟨M⟩ ∣ L(M) contiene al menos 21 miembros }
(A) L 1 , L 3 y L 4 solamente
(B) L 1 y L 3 solamente
(C) L 2 y L 3 solamente
(D) L 2 , L 3 y L 4 solamente
Respuesta: (A)
Explicación : L 1 = { ⟨M⟩ ∣ L(M)=∅ } es un problema de vacío de TM, que es indecidible , por el teorema de Rice ya que es un problema no trivial.
L 2 = { ⟨M,w,q⟩ ∣ M en la entrada w alcanza el estado q en exactamente 100 pasos } es decidible ya que podemos ejecutar el TM durante 100 pasos y ver si alcanza el estado q.
L 3 = { ⟨M⟩ ∣ L(M) no es recursivo } es indecidible según el teorema de Rice.
L 4 = { ⟨M⟩ ∣ L(M) contiene al menos 21 miembros } es indecidible. Puede o no detenerse .
Sólo L 2 es decidible.
La opción (A) es correcta.
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