Reconocimiento y complementos

Question

Estoy aprendiendo sobre las Máquinas de Turing, la decidibilidad y el reconocimiento, y leo que si un idioma es reconocible, su complemento a veces es reconocible. Realmente no entiendo cómo podría ser esto, ¿alguien puede darme un ejemplo en el que un idioma tenga un complemento reconocible y un complemento irreconocible? ¡Gracias!

Answer 1

Ejemplo 1. El lenguaje vacío es reconocible y su complemento (el lenguaje que contiene todas las palabras) también es reconocible.

Ejemplo 2. Cualquier idioma regular es reconocible y, dado que los idiomas regulares están cerrados bajo complemento , su complemento también es reconocible.

Ejemplo 3. El idioma$H = \{ \langle T, x \rangle : T \mbox{ is a Turing Machine}, x \in \{0,1\}^*, T(x) \mbox{ halts}\}$es reconocible. Para reconocer$H$ basta con construir una máquina de Turing $M$ que comprueba si $T$ es una descripción válida de una máquina de Turing, simula $T$ en $x$ Hasta que $T(x)$ se detiene (posiblemente para siempre) y acepta.

El complemento $\overline{H}$ de $H$Sin embargo, no es reconocible como si fuera reconocible una máquina de Turing. $M'$ por $\overline{H}$, Juntos con $M$, permitiría resolver el problema de la detención . Para hacerlo, simplemente simule en paralelo$M$ y $M'$ hasta que uno de ellos acepta.