Propiedades positivas de cierre (cerrado bajo estas operaciones):
* unión: Si L1 y L2 son reconocibles de Turing, entonces L1 ∪ L2 también es reconocible. Puede simular tanto las máquinas Turing para L1 y L2 en paralelo. Si se acepta, la máquina combinada acepta.
* Concatenación: Si L1 y L2 son reconocibles de Turing, entonces L1L2 también es reconocible. Esto es un poco más complicado. Puede dividir no deterministamente la cadena de entrada en dos partes, luego ejecutar las máquinas Turing para L1 y L2 en esas partes. Si ambos aceptan, entonces la máquina combinada acepta.
* Kleene Star: Si L es reconocible a Turing, entonces L* también es reconocible. Similar a la concatenación, puede dividir de forma no determinista la cadena de entrada en cero o más partes y probar si cada parte está en L.
* reversión: Si L es reconocible a Turing, entonces L
Propiedades de cierre negativo (no cerrado bajo estas operaciones):
* Intersección: Los idiomas reconocibles de Turing están * no * cerrados bajo intersección. Esto significa que si L1 y L2 son reconocibles de Turing, L1 ∩ L2 no es * necesariamente * reconocible. Sin embargo, si*ambos*L1 y L2 son turing-*decidibles*, entonces L1 ∩ L2 es decidable (y, por lo tanto, también es reconocible a Turing).
* Complementación: Los idiomas reconocibles de Turing están * no * cerrados bajo complementación. Si L es reconocible a Turing, ¬l (el complemento de L) es * no necesariamente * reconocible.
* Un lenguaje L es decidable (recursivo) si y solo si tanto L y ¬l son reconocibles (recursivamente enumerables). Esta es una conexión crucial entre los idiomas reconocibles y decidibles.
En resumen:
| Operación | ¿Cerrado? | Explicación |
| ----------------- | --------- | ------------------------------------------------------------------------------------------- |
| Unión | SÍ | Simule ambas máquinas en paralelo, acepte si acepta. |
| Concatenación | SÍ | Entrada y prueba de división no determinada y prueba cada parte. |
| Kleene Star | SÍ | La entrada no determinada no determinada en múltiples partes y prueba cada parte. |
| Inversión | SÍ | Invierta la entrada y ejecute el TM. |
| Intersección | No | Puede fallar. Requiere que ambos idiomas sean decidibles para el cierre. |
| Complementación | No | El complemento de un lenguaje reconocible de Turing no siempre es reconocible. |
¿Por qué no están cerradas la intersección y la complementación?
El problema se deriva del hecho de que las máquinas de Turing para los idiomas reconocibles de Turing pueden recorrer para siempre.
* Intersección: Si una de las máquinas buce en una entrada en particular, la máquina combinada también podría recorrer, incluso si la otra máquina eventualmente rechazara (lo que significa que la entrada * no * en la intersección). Necesita una forma de saber * cuándo * dejar de esperar una máquina que pueda estar en bucle para siempre.
* Complementación: Una máquina de Turing para L acepta, rechaza o buce en una entrada. Para reconocer el complemento ¬l, debe * rechazar * todas las cadenas aceptadas por l y * aceptar * todas las cadenas rechazadas * o enrolladas en * por L. No puede distinguir de manera confiable entre una máquina que * rechazará eventualmente y una que va a recorrer para siempre. Debería ser capaz de saber de alguna manera * cuando * una máquina va al bucle, lo que generalmente es imposible.
Ejemplo que demuestre la no clasificación bajo complementación:
Considere el problema de detención, que es reconocible por Turing (una máquina de Turing puede simular otra máquina de Turing y aceptar si se detiene). El complemento del problema de detención es * no * reconocible. Si lo fuera, entonces el problema de detención sería decidable (ya que tanto el problema de detención como su complemento serían reconocibles), lo que sabemos que es falso.