Dla dowolnego języka istnieje takie, że ale

Próbuję wymyślić dowód na następujące kwestie:

Dla każdego języka $A$ istnieje język $B$ , tak że $A \le_{\mathrm{T}} B$ a B $\nleq_{\mathrm{T}} A$ .

Myślałem o pozwoleniu $B$ być $A_{\mathrm{TM}}$ , ale zdaję sobie sprawę, że nie wszystkie języki Turing można zredukować do $A_{\mathrm{TM}}$ , więc $A \le _T B$ nie wytrzyma. Jaki mam inny wybór $B$ , który pozwoliłby mi napisać TM, która użyłaby wyroczni, aby $B$ zdecydował się na $A$ ?

Dzięki!

computability reductions undecidability użytkownik1354784
źródło

Co powiesz na

B = N P^{A}

$B = NP^A$ ?

Eugene

Pomyśl o problemu stopu na Maszyna Turinga z oracle

A

$A$ .

Willard Zhan

@ user1354784 Maszyny Turinga z wyrocznią

A

$A$ można wymienić. Spróbuj więc użyć standardowej diagonalizacji, gdzie jedyną zmianą jest to, że dla każdego

α \in Σ^{*}

$\alpha\in\Sigma^*$ ,

M_{α}

$M_\alpha$ reprezentuje wyrocznię TM z wyrocznią

A

$A$ zamiast normalnej TM.

Willard Zhan,

@DavidRicherby Tak, ale B nie jest naprawiony, jest zbudowany wiedząc, co to jest A. Jeśli otrzymamy trochę A, budujemy B, które akceptuje każdą wyrocznię TM z wyrocznią dla tego konkretnego A, który akceptuje ciągi w A. Jeśli otrzymamy inne A, lista TM w B będzie inna.

user1354784,

@ user1354784 Dokładnie. Miałem na myśli ten komentarz jako kolejne wyjaśnienie, dlaczego nie możemy przyjąć jak zasugerowałeś (i już odrzuciłeś, z innego powodu) w swoim pytaniu. Zapomniałem wyjaśnić, że o to mi chodziło - przepraszam za zamieszanie.

B = A_{T M}

$B=A_{\mathrm{TM}}$

David Richerby,

Odpowiedzi:

Niech , skok Turing od . Jest to podstawowy wynik w teorii stopni Turinga. $B=A'$ $A$

Bjørn Kjos-Hanssen
źródło

Przed zanurzeniem się w dobrą odpowiedź - mianowicie, że możemy relatywizować problem zatrzymania, aby przypisać każdemu językowi język taki, że (między innymi) - warto zobaczyć głupią odpowiedź: $X$ $X'$ $X<_TX'$

Cantor pokazał, że istnieje niezliczona ilość języków.
Ale każdy konkretny język może obliczyć tylko policzalnie wiele języków: pojedyncza maszyna Turinga może przynieść tylko jedną redukcję z danego języka , a istnieje tylko policzalnie wiele maszyn Turinga. $A$ $A$

Tak więc wiemy, nie wykonując żadnej poważnej pracy, że:

Dla każdego języka , większość (= wszystkie) ale przeliczalnie wiele języków usatysfakcjonować . $A$ $B$ $B\not\le_TA$

Teraz łączymy to z Turinga join : podane języki , łączenia składa się z „przeplatania” i . Istnieją różne sposoby jego zdefiniowania - np. Myśląc o i jako zbiorach naturali, zwykle pozwalamy - ale ważną cechą jest to, że (i tak naprawdę to ich -najmniejsza górna granica) . $X,Y$ $X\oplus Y$ $X$ $Y$ $X$ $Y$ $X\oplus Y=\{2i: i\in X\}\cup\{2i+1: i\in Y\}$ $X\oplus Y\ge_TX,Y$ $\le_T$

Możemy więc zastosować powyższe, aby uzyskać:

Dla każdego języka , większość (= wszystko ale przeliczalnie wielu) Języki usatysfakcjonować . $A$ $B$ $A<_TA\oplus B$

Rodzi to następnie pytanie o nie-głupi dowód, a mianowicie naturalny sposób na stworzenie języka znacznie bardziej skomplikowanego niż dany, i do tego właśnie służy skok Turinga; ale warto zrozumieć ten niekonstruktywny argument sam w sobie.

Noah Schweber
źródło