Quale lingua indecidabile $ B $ è riducibile al suo complemento?

Question

Ho riscontrato un problema che chiede di dare un esempio di un linguaggio indecididabile $ B $ tale che $ b \ leq_m\ overline {b} $ ...

Tuttavia, ho potuto trovare difficile costruire un esempio ... La mia difficoltà è quella data un linguaggio riconoscibile indecidabile ma tinger riconoscibile, dire $ a_ {tm} $ , il suo complemento $ \ Overline {A_ {TM}} $ non tura riconoscibile e loop.Se riducono una lingua del genere (dì $ x \ in a_ {tm} \ leq_m y \ in \ in \ overline {a_ {tm}} $ , la classe istanza <="container di matematica"> $ y \ in \ overline {A_ {tm}} $ non può essere riconosciuto da alcun TM (dal momento che per definizione, $ \ Overline {A_{Tm}} $ è looping) ...

Qualsiasi aiuto?

Answer 1

Let $ H $ Sii la lingua di tutte le macchine Turing che si fermano sull'input vuoto. Chiaramente $ h $ è un indecidabile.

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

Chiaramente $ l $ è indecidabile. Se $ L $ è stato decidabile, quindi una macchina di Turing $ m $ per $ L $ Imparare anche l'esistenza di una macchina di Turing $ m '$ che decide $ H $ . $ M '$ con ingresso $ T $ Simula semplicemente $ M $ con ingresso $ (1, t) $ .

Inoltre, per una macchina di Turing $ T $ e $ x \ in \ {0,1 \} $ < / span> Abbiamo: $$ (x, t) \ in l \ iff (1-x, t) \ non \ in l \ iff (1-x, t) \ in \ overline {l}. $$

Questo, combinato con il fatto che possiamo decidere se una determinata parola codifica una macchina di Turing valida, mostra che $ l $ è riducibile a $ \ overline {l} $ .