Untuk bahasa

Saya mencoba memberikan bukti sebagai berikut:

Untuk bahasa apapun $A$ , terdapat bahasa $B$ sehingga $A \le_{\mathrm{T}} B$ tapi B $\nleq_{\mathrm{T}} A$ .

Saya berpikir untuk membiarkan $B$ menjadi $A_{\mathrm{TM}}$ , tetapi saya menyadari bahwa tidak semua bahasa Turing dapat direduksi menjadi $A_{\mathrm{TM}}$ , jadi $A \le _T B$ tidak akan berlaku. Pilihan $B$ apa lagi yang saya miliki yang memungkinkan saya untuk menulis TM yang menggunakan oracle untuk $B$ untuk memutuskan $A$ ?

Terima kasih!

computability reductions undecidability pengguna1354784
sumber

Bagaimana dengan ?

B = N P^{A}

$B = NP^A$

Eugene

Pikirkan masalah terputus-putus pada Turing mesin dengan oracle .

A

$A$

Willard Zhan

@ user1354784 Mesin Turing dengan oracle dapat disebutkan. Jadi coba gunakan diagonalisasi standar, di mana satu-satunya perubahan adalah untuk setiap , mewakili oracle TM dengan oracle alih-alih TM normal.

A

$A$

α \in Σ^{*}

$\alpha\in\Sigma^*$

M_{α}

$M_\alpha$

A

$A$

Willard Zhan

@ DavidRicherby Ya, tapi B tidak diperbaiki, ia dibangun dengan mengetahui apa itu A. Jika kita diberi beberapa A, kita membangun B yang menerima setiap oracle TM dengan oracle untuk A spesifik ini yang menerima string dalam A. Jika kita diberi A yang berbeda, daftar TM di B akan berbeda.

user1354784

@ user1354784 Tepat. Maksud saya komentar itu sebagai penjelasan lain mengapa kami tidak bisa menggunakan seperti yang Anda sarankan (dan sudah ditolak, karena alasan berbeda) dalam pertanyaan Anda. Saya lupa menjelaskan bahwa itulah yang saya sampaikan - maaf atas kebingungan di sana.

B = A_{T M}

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

David Richerby

Jawaban:

Misalkan , Turing melompat dari . Ini adalah hasil dasar dalam teori derajat Turing. $B=A'$ $A$

Bjørn Kjos-Hanssen
sumber

Sebelum menyelam ke jawaban yang baik - yaitu, bahwa kita dapat merelatifkan masalah penghentian untuk menetapkan ke setiap bahasa bahasa sedemikian rupa sehingga (antara lain) - ada baiknya melihat jawaban konyol : $X$ $X'$ $X<_TX'$

Cantor menunjukkan bahwa ada banyak bahasa yang tak terhitung jumlahnya.
Tetapi setiap bahasa tertentu hanya dapat menghitung banyak bahasa: satu mesin Turing hanya dapat menghasilkan satu pengurangan dari bahasa diberikan , dan hanya ada banyak mesin Turing. $A$ $A$

Jadi sebenarnya kita tahu, tanpa melakukan pekerjaan serius, bahwa:

Untuk setiap bahasa $A$ , sebagian besar (= semua tapi countably banyak) bahasa $B$ memuaskan $B\not\le_TA$ .

Sekarang kita menggabungkan ini dengan Turing bergabung : bahasa diberikan $X,Y$ , bergabung $X\oplus Y$ terdiri dari "interleaving" $X$ dan $Y$ . Ada berbagai cara untuk mendefinisikannya - misalnya berpikir $X$ dan $Y$ sebagai set natural, kita biasanya membiarkan $X\oplus Y=\{2i: i\in X\}\cup\{2i+1: i\in Y\}$ - tetapi fitur penting apakah itu $X\oplus Y\ge_TX,Y$ (dan pada kenyataannya adalah $\le_T$ batas terakhirnya).

Jadi kita bisa menerapkan hal di atas, untuk mendapatkan:

Untuk setiap bahasa $A$ , sebagian besar (= semua tapi countably banyak) bahasa $B$ memuaskan $A<_TA\oplus B$ .

Hal ini kemudian menimbulkan pertanyaan tentang memberikan bukti yang tidak bodoh , yaitu cara alami untuk menghasilkan bahasa yang lebih rumit daripada bahasa tertentu, dan inilah tujuan lompatan Turing; tetapi perlu memahami argumen non-konstruktif ini sendiri.

Noah Schweber
sumber