Un lenguaje L se llama decidible por Turing (o simplemente decidible), si existe una Máquina de Turing M tal que en la entrada x, M acepta si x ∈ L, y M rechaza lo contrario. L se llama indecidible si no es decidible.
¿Cuál de las siguientes opciones es falsa?
(A) La clase de lenguajes decidibles está cerrada bajo complemento.
(B) La clase de lenguajes decidibles es cerrada bajo unión
(C) La clase de lenguajes decidibles es cerrada bajo intersección
(D) Ninguno de estos
Respuesta: (D)
Explicación: La clase de lenguajes decidibles es cerrada bajo unión, intersección y complementación
La opción (D) 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