Que linguagem indecidável $ b $ é reduzível ao seu complemento?

Question

Eu encontrei um problema que pede para dar um exemplo de uma linguagem indecidável $ B $ tais que $ b \ leq_m\ overline {b} $ ...

No entanto, eu poderia achar difícil construir um exemplo ... Minha dificuldade é que, dado uma linguagem reconhecível, mas Turing, digamos $ a_ {tm} $ , seu complemento $ \ overline {a_ {tm}} $ não está tentando reconhecível e loops.Se eu reduzir tal linguagem (digamos $ x \ in A_ {tm} {tm \ in \ spany {a_ {tm}} $ , a instância $ y \ in \ overline {a_ {tm}} $ não pode ser reconhecido por qualquer tm (já que por definição, $ \ overline {a_{Tm}} $ está loop) ...

Qualquer ajuda?

Answer 1

Deixe $ h $ Seja o idioma de todas as máquinas de Turing que parassem na entrada vazia. Claramente $ h $ é indecidável.

Deixe $ l={(1, t): t \ in h \} \ cope \ {(0, t): t \n\ in h \} $ .

claramente $ l $ é indecidável. Se $ l $ fossem decidíveis, depois uma máquina de Turing $ m $ para $ l $ também implicaria a existência de uma máquina de Turing $ m '$ que decide $ H $ . $ m '$ com entrada $ t $ simplesmente simula $ M $ com entrada $ (1, t) $ .

Além disso, para uma máquina de Turing $ t $ e $ x \ in \ {0,1 \} $ < / span> temos: $$ (x, t) \ in l \ iff (1-x, t) \ não \ in l \ ff (1-x, t) \ in \ overline {l}. $$

Isso, combinado com o fato de que podemos decidir se uma determinada palavra codifica uma máquina de Turing válida, mostra que $ l $ é redutível para $ \ overline {l} $ .