Mostralo per ogni lingua Esiste una lingua più dura

Question

Ho trovato questo problema che non potevo capire ... per ogni lingua $ A $ , dovrebbe essere una lingua $ B $ tale che:

$$ A \ Leq_T B $$

Ma:

$$ B \ non \ leq_t a $$

Se è $ a \ leq_tb $ e $ b \ leq_t a $ , questo è facileDal momento che possiamo semplicemente lasciare che $ B:=bar {a} $ , ma per quanto sopra non potevo pensare a nulla.Qualsiasi aiuto?

Answer 1

Ci sono alcuni modi per affrontare questo.

È possibile utilizzare un argomento di conteggio per dimostrarlo per ogni $ A $ esiste $ B $ Tale che $ B \ nleq_t a $ . Let $ l_a={B | B \ le_t a \} $ Dennare il set di tutte le lingue riducibile a $ A $ . Mostra che $ f: l_a \ RightArrow \ MathBB {n} $ che maps lingue $ b \ in l_a $ a $ N $ in modo tale che $ m_n $ è una riduzione da $ B $ a $ A $ è un'iniezione e conclude che esiste una lingua al di fuori di $ L_a $ . Successivamente, vuoi renderlo paragonabile a $ A $ . Possiamo ottenere una tale lingua con l'operatore di join:

$ a \ sqcup b={0w | w \ in a \} \ cup \ {1w | w \ in b \} $ . Lascio per dimostrare che $ a \ sqcup B $ è il minimo superiore per $ A, B $ , ovvero $ a, b \ le_t a \ sqcup B $ e inoltre per ogni $ l $ in modo tale che $ a, b \ le_t l $ abbiamo $ a \ sqcup b \ le l $ < / span> (ti importa solo del primo). Mostra che se $ B \ nleq_t a $ quindi $ a \ sqcup b \ nleq_t a $ . .

Un altro modo per dimostrare che questo è usare il Jump Operator . Dobbiamo introdurre la nozione di Oracle Machines , e poi mostrano che $ B=sinistra \ {\ sinistra (m ^ a, w \ destra) | \ testo {$ m ^ a $ halts su $ w $} \ destra \} $ è una lingua rigorosamente più dura. La prova è identica all'individità del problema di arresto standard, solo che ora mostriamo la proprietà più forte che nessuna macchina con accesso oracle a $ A $ può decidere la classe $ B $ .

È inoltre possibile costruire direttamente una tale lingua attraverso la diazionalità. Definisci $ B=Sinistra \ {n | M_N (N) \ Notin A \ Destra \} $ . Abbiamo costruito $ B $ in modo tale che qualsiasi funzione calcolabile $ M_N $ non riesce a essere una riduzione dalla classe $ B $ a $ a $ su almeno un ingresso (in particolare, la codifica della riduzione). Ora puoi utilizzare l'operatore Iscriviti per renderli comparabili.