Apakah ada hasil dalam teori komputasi yang tidak merelatifkan?

Saya sedang membaca makalah Andrej Bauer Langkah Pertama dalam Teori Komputasi Sintetis . Dalam kesimpulan dia mencatat itu

Aksiomasiisasi kami memiliki batas: tidak dapat membuktikan hasil apa pun dalam teori komputabilitas yang gagal dikaitkan dengan perhitungan oracle. Ini karena teori dapat ditafsirkan dalam varian topos efektif yang dibangun dari fungsi rekursif parsial dengan akses ke oracle.

Ini membuat saya bertanya-tanya tentang hasil non-relativizing dalam komputasi. Semua hasil yang saya tahu dari teori komputabilitas melakukan relativize ke komputasi dengan nubuat.

Adakah hasil dalam teori komputabilitas yang tidak terelatifkan? Yaitu hasil yang berlaku untuk komputabilitas tetapi tidak berlaku untuk komputabilitas relatif terhadap beberapa oracle?

Maksud saya adalah teorema yang dikenal dalam teori komputabilitas, bukan pernyataan yang dibuat-buat. Jika gagasan relativization tidak masuk akal untuk hasilnya maka itu bukan apa yang saya cari.

Menarik juga untuk mengetahui apakah hasilnya dapat dinyatakan dalam bahasa Teori Komputasi Sintetis atau tidak.

computability relativization Anonim
sumber

Semua orang tahu tentang hasil non-relativizing dalam teori kompleksitas seperti IP = PSPACE. Saya bertanya tentang teori komputabilitas yang tidak relativizing , bukan hasil teori kompleksitas .

Anonim

@Erfan: Komentar Anda tidak relevan dengan pertanyaan. Pertanyaan saya adalah tentang teori komputabilitas, Anda berbicara tentang teori kompleksitas. Saya mencari hasil non-reletivizing, teorema hirarki waktu memang relativize. Jika Anda memiliki pertanyaan tentang teorema hierarki waktu dan relatisasi, Anda dapat memposting pertanyaan terpisah.

Anonim

Hal-hal yang relevan: dugaan Homogenitas yang dirumuskan oleh H. Rogers telah disangkal di Richard A. Shore; Dugaan homogenitas (1979): terdapat derajat Turing sedemikian rupa sehingga bukan isomorfik hingga (struktur derajat Turing dengan sebagian pesan ). Lihat pertanyaan serupa di lo.logic

a

$\mathbf{a}$

D (\geq a)

$\mathcal{D}(\geq \mathbf{a})$

D

$\mathcal{D}$

\leq_{T}

$\leq_{T}$

Marzio De Biasi

Pertanyaan bagus :-)

Andrej Bauer

@ Marszio: Menarik. " Jadi ini berarti ada kalimat orde pertama dalam bahasa yang hanya berisi yang benar tentang derajat Turing, tetapi yang salah jika Anda merelatifkan kalimat ke derajat Turing untuk beberapa (dan tentu saja , bekerja dalam derajat Turing setara dengan memberikan semua mesin Turing akses ke sebagai oracle). Oleh karena itu, bukti bahwa benar tidak dapat direlatifikasi ke . $\varphi$ $\leq_T$ $\geq_Tx$ $x$ $\geq_Tx$ $x$ $\varphi$ $x$ "Tetapi tidak benar-benar menghasilkan teori komputabilitas, ia dimasak untuk teorema meta.

φ

$\varphi$

Anonim

Jawaban:

Teorema Penyematan Higman: Grup yang disajikan secara komputabel yang dihasilkan secara tepat adalah subkelompok yang dihasilkan secara finis dari kelompok-kelompok yang disajikan secara halus. Selain itu, setiap grup yang disajikan secara komputabel (bahkan yang dihasilkan secara signifikan) adalah subkelompok dari grup yang disajikan secara halus.

Perhatikan bahwa pernyataan ini dapat direlatifkan ke: " Grup yang ditampilkan secara (dengan beberapa oracle ) adalah subkelompok yang dihasilkan secara halus dari kelompok yang disajikan dengan baik," tetapi tidak, karena orang dapat membuktikan bahwa untuk beberapa tidak dapat dihitung ada Kelompok -computably disajikan yang tidak disajikan secara computably. $O$ $O$ $O$ $O$

Memang, saya pikir setiap hasil non-merelatifkan teori komputabilitas harus memiliki sesuatu rasa ini, karena beberapa bagian dari hasil atau bukti yang harus entah bagaimana "memakukan" computability benar dari computability dengan oracle . Dalam hal ini, keterbatasanlah yang menghasilkan "kemampuan komputasi yang sebenarnya". Perhatikan bahwa, seperti yang diminta oleh Scott Aaronson, hasil ini tidak sesuai dengan model komputasi yang biasa (mesin Turing, RAM, dll.), Tetapi tidak relativize (sekali lagi, karena semua model komputasi "aktual" yang biasa berbagi beberapa "properti finiteness" yang umum). $O$

Di sisi lain, orang mungkin berpendapat bahwa ini "tidak masuk akal" untuk pertanyaan ini, karena lebih mirip dengan definisi komputabilitas menggunakan kelompok daripada itu adalah "hasil dari teori komputabilitas." Di sisi lain, itu adalah definisi dari kemampuan komputasi yang kuat untuk model namun tidak relatif . (Berbeda dengan, katakanlah, karakterisasi Kleene dari fungsi yang dapat dihitung yang dengan mudah relativis, dengan hanya menambahkan fungsi karakteristik oracle Anda ke rangkaian fungsi pembangkit. Tampaknya tidak ada operasi analog untuk grup dalam konteks Higman Embedding.)

Joshua Grochow
sumber

Apakah finiteness (vs tak terhingga) yang membedakan contoh Anda, atau dapat dihitung (vs tidak terhitung)?

András Salamon

Maafkan ketidaktahuan saya, tetapi apakah teorema Higman seragam? Yaitu, diberikan grup yang disajikan secara komputasi, dapatkah kita menghitung secara seragam grup yang dihasilkannya yang berisi itu?

Andrej Bauer

Ooops, harap ganti "dihasilkan secara halus" dengan "disajikan secara halus" dalam pertanyaan saya. Itu kesalahan sepele. Yang saya pikirkan adalah apakah kita dapat mengganti "yang disajikan dengan baik" dengan sesuatu yang sedikit lebih umum.

Andrej Bauer

@AndrewMorgan: Saya setuju dengan awal argumen Anda tetapi tidak setuju dengan kesimpulan Anda. Seringkali cukup berguna bahwa adalah -lengkap. Saya tidak menganggap relativiasi Cook-Levin sama sekali tidak wajar ... Saya sangat menyukai saran Andrej dan kami akan memikirkannya ...

S A T^{O}

$SAT^O$

N P^{O}

$NP^O$

Joshua Grochow

@AndrewMorgan: Setuju. Saya akan berpikir bahwa simpul genus akan menjadi kandidat yang baik :).

Joshua Grochow

Ini adalah sesuatu yang sering saya tanyakan!

Jika dengan "menghasilkan teori komputabilitas," yang Anda maksud adalah hasil yang tidak berubah sehubungan dengan pilihan model mesin (mesin Turing, mesin RAM, dll.), Maka saya tidak tahu satu contoh pun dari hasil seperti itu, dan saya pasti akan ingat jika aku melihatnya.

Jawaban terdekat yang dapat saya sarankan untuk sebuah jawaban adalah: Saya pikir ada banyak pertanyaan menarik dalam teori komputabilitas yang mungkin bergantung pada model mesin. Sebagai contoh: apakah fungsi Sibuk Berang-berang, dengan definisi yang biasa dalam hal mesin Turing, sering kali aneh? Apakah nilai BB (20) tidak tergantung pada ZFC? Apa pun jawaban untuk pertanyaan-pertanyaan ini, mereka pasti bisa berbeda untuk analog yang relatif dari fungsi BB.

Scott Aaronson
sumber

Berikut ini contoh yang kurang lebih sepele: Pertimbangkan masalah penghentian untuk mesin Turing yang secara khusus dilarang (dengan definisi model komputasi) mengakses oracle. Ini relatif tidak dapat diputus baik untuk oracle dan oracle sepele, namun itu relatif relatif terhadap oracle untuk masalah penghentian. (Masalah itu sendiri tidak berubah relatif terhadap oracle karena tidak dapat mengakses oracle, tetapi TM (tidak dibatasi) yang memutuskan masalah menjadi lebih kuat mengingat oracle.)

Ada banyak contoh lain juga. Hanya bermain dengan model perhitungan sedikit dan Anda dapat menemukan hasil serupa lainnya.

Philip White
sumber

Hanya ingin tahu: apa sebenarnya yang salah dengan jawaban ini? Mungkin downvoters tidak percaya bahwa ada kemungkinan untuk melarang mesin Turing mengakses oracle dan memerlukan penjelasan lebih lanjut tentang ini?

Philip White

Sepertinya tidak ada definisi relativisasi yang sangat adil untuk memungkinkan mesin memiliki oracle tetapi kemudian tidak mengizinkannya menggunakan oracle.

David Eppstein

Menarik meski bukan yang saya cari. Saya mencari hasil yang diketahui dalam teori komputabilitas yang tidak merelatifkan, bukan argumen tentang cara memasak hasil seperti itu.

Anonim

Pertimbangkan pernyataan berikut: H (menghentikan masalah untuk mesin Turing tanpa nubuat) tidak dapat dihitung. Di sisi lain H dapat dihitung relatif terhadap masalah oracle yang terhenti. Sekalipun kita menganggap ini sebagai cara merelatifkan pernyataan itu, itu tidak menarik. Mungkin ada cara yang serupa untuk merelatifkan pernyataan yang membuatnya salah. Relativisasi bukan hanya melampirkan oracle di suatu tempat. Relativisasi menarik ketika mempertahankan beberapa kelas argumen yang menarik, jadi jika sebuah pernyataan tidak relativize kita tahu bahwa kelas argumen tidak dapat membuktikan pernyataan itu.

Kaveh

Ambil contoh metode relativization dalam BGS. Ini menarik karena mempertahankan argumen diagonalisasi sederhana sehingga mereka tidak dapat menyelesaikan P vs NP. Jika relatisasi tidak mempertahankan argumen seperti itu maka mungkin bukan cara yang menarik untuk merelatifkan pernyataan. Relativisasi yang baik harus bertahan dari banyak argumen yang diketahui dan hasil yang terbukti mungkin, semakin kurang dipertahankan semakin kurang menariknya jadinya.

Kaveh