Pengurangan di antara Masalah yang Tidak Diputuskan

Saya minta maaf jika pertanyaan ini memiliki beberapa jawaban sepele yang saya lewatkan. Setiap kali saya mempelajari beberapa masalah yang telah terbukti tidak dapat diputuskan, saya mengamati bahwa buktinya bergantung pada pengurangan ke masalah lain yang telah terbukti tidak dapat diputuskan. Saya mengerti bahwa itu menciptakan semacam urutan pada tingkat kesulitan suatu masalah. Tetapi pertanyaan saya adalah - apakah sudah terbukti bahwa semua masalah yang tidak dapat diputuskan dapat direduksi menjadi masalah lain yang tidak dapat diputuskan. Apakah tidak mungkin ada masalah yang tidak dapat dipastikan yang dapat terbukti tidak mengurangi masalah yang tidak dapat diputuskan lainnya (Oleh karena itu untuk membuktikan ketidakpastian masalah tersebut, seseorang tidak dapat menggunakan pengurangan). Jika kita menggunakan reduksi untuk membuat urutan pada tingkat komputabilitas maka masalah ini tidak dapat diberikan gelar seperti itu.

computability reductions undecidability swarnim_narayan
sumber

Jawaban singkat: jauh dari sepele! Lihatlah hierarki aritmatika .

Hendrik Jan

Bagaimana ini: Jika

adalah bahasa dan diputuskan

menjadi elemen terkecil di

. Kemudian

direduksi (dan sebaliknya) untuk

. Jika Anda juga menambahkan elemen ke

(katakanlah elemen terkecil tidak dalam

), maka Anda memiliki pengurangan 1-1.

L

$L$

x min L

$x \min L$

L

$L$

L^{'} = L ∖ {x}

$L' = L \setminus \{x\}$

L

$L$

L^{'}

$L'$

L

$L$

Pål GD

Jawaban:

Seperti yang disebutkan Hendrik Jan, pada kenyataannya ada beberapa tingkat ketidakpastian yang berbeda . Sebagai contoh, masalah memutuskan apakah mesin Turing berhenti pada semua input lebih sulit daripada masalah penghentian, dalam arti berikut: meskipun diberi oracle untuk masalah penghentian, kami tidak dapat memutuskan apakah mesin Turing yang diberikan berhenti pada semua input .

$P$ $P$ $P'$ $P$ $P'$

Yuval Filmus
sumber

Terima kasih atas jawabannya. Saya mengerti apa yang Anda katakan. Kita dapat membangun masalah "sulit" dari yang "sulit". Tetapi apakah skema pembangunan masalah yang lebih sulit dari masalah yang sulit (misalnya katakanlah diagonalisasi adalah salah satu skema seperti yang Anda sebutkan) harus mencakup "semua" masalah yang belum diputuskan yang ada (yaitu apakah mereka dijamin untuk membangun serangkaian semua masalah yang tidak dapat dipastikan). Apakah tidak mungkin bahwa beberapa mungkin ditinggalkan dalam konstruksi dan mereka tidak dapat dibangun dari yang tidak dapat ditentukan?

swarnim_narayan

Sebaliknya, kita tahu bahwa sebagian besar masalah akan diabaikan, karena hanya ada banyak masalah yang dapat didefinisikan, tetapi secara total banyak masalah. Lebih konkretnya, Anda bertanya bagaimana mendefinisikan masalah "sangat sulit", analog rekursi-teoretis dari kardinal besar. Jika itu yang Anda minati, ajukan pertanyaan baru yang berfokus pada aspek ini.

Yuval Filmus

Masalah serupa muncul ketika membangun hierarki fungsi rekursif yang tumbuh cepat, dalam hal ini diketahui bahwa dalam beberapa hal, tidak ada cara untuk membangun hierarki yang bagus dan lengkap.

Yuval Filmus