¿Qué lenguaje indecidible $ B $ es reducible a su complemento?

Question

Me encontré con un problema que solicita dar un ejemplo de un lenguaje indecidable $ b $ de tal que $ b \ leq_m\ Overline {b} $ ...

Sin embargo, podría encontrar difícil construir un ejemplo ... Mi dificultad es que le dio un lenguaje reconocible sin fines de tutor, por ejemplo, $ a_ {tm} $ , su complemento $ \ overline {a_ {tm}} $ no es reconocible y los bucles.Si reduce este tipo de idioma (diga $ x \ en A_ {tm} \ leq_m y \ in \ endinline {a_ {tm}} $ , la instancia $ y \ in \ Overline {A_ {tm}} $ no puede ser reconocido por ningún TM (desde definición, $ \ overline {a_{Tm}} $ está en bucle) ...

¿Alguna ayuda?

Answer 1

Let $ H $ Sé el idioma de todas las máquinas de Turing que se detienen en la entrada vacía. Claramente $ H $ es indecidible.

Let $ l={(1, t): t \ in h \ \ \ taza \ {(0, t): t \ no \ in h \ in h \ \} $ .

claramente $ l $ es indecidible. Si $ l $ fue decidible, luego una máquina de Turing $ m $ para $ l $ también implicaría la existencia de una máquina de turing $ m '$ que decide $ H $ . $ m '$ con entrada $ t $ simplemente simula $ M $ con entrada $ (1, t) $ .

Además, para una máquina de Turing $ t $ y $ x \ in \ {0,1 \} $ < / SPAN> Tenemos: $$ (x, t) \ in l \ \ iff (1-x, t) \ no \ in l \ iff (1-x, t) \ in \ overline {l}. $$

Esto, combinado con el hecho de que podemos decidir si una palabra dada codifica una máquina de turaje válida, muestra que $ l $ es reducible para $ \ Overline {l} $ .