Adakah masalah khusus yang diketahui tidak dapat dipastikan karena alasan selain diagonalisasi, referensi-diri, atau reducibilitas?

28

Setiap masalah yang tidak dapat dipastikan yang saya ketahui termasuk dalam salah satu kategori berikut:

  1. Masalah yang tidak dapat dipastikan karena diagonalisasi (referensi diri tidak langsung). Masalah-masalah ini, seperti masalah penghentian, tidak dapat diputuskan karena Anda dapat menggunakan penentu yang konon untuk bahasa untuk membangun TM yang perilakunya mengarah pada kontradiksi. Anda juga bisa mengelompokkan banyak masalah yang tidak dapat dipastikan tentang kompleksitas Kolmogorov ke dalam perkemahan ini.

  2. Masalah-masalah yang tidak dapat ditentukan karena referensi-sendiri secara langsung. Sebagai contoh, bahasa universal dapat ditunjukkan tidak dapat diputuskan karena alasan berikut: jika itu dapat ditentukan, maka akan dimungkinkan untuk menggunakan teorema rekursi Kleene untuk membangun TM yang mendapatkan encoding sendiri, tanyakan apakah ia akan menerima inputnya sendiri , lalu lakukan yang sebaliknya.

  3. Masalah yang tidak dapat diputuskan karena pengurangan dari masalah yang tidak dapat diputuskan yang ada. Contoh-contoh yang baik di sini termasuk Masalah Korespondensi Pasca Kiriman (pengurangan dari masalah penghentian) dan Entscheidungsproblem.

Ketika saya mengajarkan teori komputabilitas kepada murid-murid saya, banyak siswa juga memahami hal ini dan sering bertanya kepada saya apakah ada masalah yang dapat kami buktikan tidak dapat diputuskan tanpa akhirnya melacak kembali ke beberapa jenis tipu daya referensi diri. Saya dapat membuktikan secara tidak konstruktif bahwa ada banyak masalah tak terhingga dengan argumen kardinalitas sederhana yang menghubungkan jumlah TM dengan jumlah bahasa, tetapi ini tidak memberikan contoh spesifik dari bahasa yang tidak dapat ditentukan.

Adakah bahasa yang diketahui tidak dapat ditentukan karena alasan yang tidak tercantum di atas? Jika demikian, apa sajakah itu dan teknik apa yang digunakan untuk menunjukkan keraguan mereka?

computability proof-techniques undecidability templatetypedef
sumber
@ EvilJS Pemahaman saya adalah bahwa bukti ketidakpastian di sana melibatkan kemampuan untuk mensimulasikan TM, meskipun mungkin saya salah?
templatetypedef
Anda dapat mengatakan teorema Rice mungkin tidak cocok dengan salah satu kategori ini, tetapi bukti teorema itu cocok.
Ryan
1
@ EvilJS Itu poin yang bagus. Sungguh, yang saya cari di sini adalah apakah ada beberapa teknik yang secara fundamental berbeda yang bisa kita gunakan. Akan lebih baik, misalnya, jika seseorang mengidentifikasi masalah sebagai tidak dapat diputuskan dalam kasus di mana masalah tersebut tidak memiliki hubungan yang diketahui dengan referensi-sendiri TM atau argumen tipe Godeling. Jika yang terbaik yang bisa kita lakukan adalah "kita sudah menemukan ini sejak lama, kemudian menyadari bahwa lebih mudah untuk membuktikannya dengan cara lain," bahwa dalam arti akan menjadi jawaban - tiga teknik di atas secara mendasar menjelaskan semua bukti dari ketidakpastian yang kita ketahui.
templatetypedef
2
f(n)n
1
@YuvalFilmus Mungkin saya terlalu ketat di sini, tapi itu terdengar seperti argumen tipe diagonal bagi saya: Anda membangun fungsi yang didefinisikan berbeda dari semua fungsi yang dihitung oleh TM.
templatetypedef

Jawaban:

10

Ya, ada buktinya. Mereka didasarkan pada Teorema Dasar Rendah .

Lihat jawaban ini untuk Apakah ada bukti keraguan tentang masalah penghentian yang tidak bergantung pada referensi-diri atau diagonalisasi? pertanyaan tentang sejarah untuk lebih.

Kaveh
sumber
Jika ada yang tertarik dengan teknik-teknik canggih dalam teori komputabilitas, maka periksa buku Robert I. Soare, Kumpulan dan Derajat yang Dapat Dihitung Secara Rekursif dan Teori dan Aplikasi Komputasi .
Kaveh
Koreksi saya jika saya salah, tetapi bukankah bukti teorema dasar rendah melibatkan penerapan fungsional pada dirinya sendiri dan menanyakan apakah itu tidak menghasilkan nilai? Jika demikian, bukankah ini hanya lapisan tipuan di atas argumen diagonal?
templatetypedef
@ templatetypedef, saya bukan ahli tapi sejauh yang saya mengerti tidak. Lihat misalnya halaman 109 dalam buku Soare.
Kaveh
@templatetypedef, ps1: ada beberapa ketidakjelasan dalam pertanyaan tentang apa yang kita anggap diagonalisasi. Jika kita tidak berhati-hati, kita dapat memperluas apa yang kita anggap sebagai diagonalisasi setiap kali kita melihat sesuatu yang tidak. Ambil misalnya metode prioritas atau metode umum membangun objek bagian demi bagian dengan cara untuk menghindari persamaan dengan objek apa pun dari kelas tertentu.
Kaveh
2
@ David, :) Saya membuka halaman dari buku yang ingin saya bagikan, klik tombol bagikan di atas, dan hapus parameter kecuali dari iddan pgdari tautan.
Kaveh
0

ini bukan jawaban afirmatif, tetapi upaya pada sesuatu yang dekat dengan apa yang diminta melalui sudut kreatif. ada beberapa masalah dalam fisika sekarang yang "jauh" dari formulasi matematis / teoritis dari keraguan, dan mereka tampaknya semakin "jauh" dari dan "sedikit mirip dengan" formulasi asli yang melibatkan masalah penghentian, dll .; tentu saja mereka menggunakan masalah penghentian pada akar tetapi rantai penalaran telah menjadi semakin jauh dan juga memiliki aspek / sifat "terapan" yang kuat. sayangnya belum ada survei hebat di bidang ini. masalah baru-baru ini yang "mengejutkan" terbukti tidak dapat dipungkiri dalam fisika yang telah menarik banyak perhatian:

Kesenjangan spektral — perbedaan energi antara keadaan dasar dan keadaan tereksitasi pertama dari suatu sistem — adalah pusat bagi fisika banyak-tubuh kuantum. Banyak masalah terbuka yang menantang, seperti dugaan Haldane, pertanyaan tentang keberadaan fase cair spin topologi yang terpetakan, dan dugaan celah Yang-Mills, menyangkut kesenjangan spektral. Masalah-masalah ini dan lainnya adalah kasus-kasus khusus dari masalah kesenjangan spektral umum: mengingat Hamiltonian dari sistem banyak-tubuh kuantum, apakah itu gaped atau gapless? Di sini kami membuktikan bahwa ini adalah masalah yang tidak dapat dipastikan. Secara khusus, kami membangun keluarga sistem spin kuantum pada kisi dua dimensi dengan interaksi yang tidak berubah, tetangga terdekat, di mana masalah kesenjangan spektral tidak dapat diputuskan. Hasil ini meluas ke ketidakpastian sifat-sifat energi rendah lainnya,

apa yang tampaknya Anda amati dalam pertanyaan adalah bahwa (tidak resmi) bukti keraguan semua memiliki struktur "referensi diri" tertentu, dan ini telah secara formal terbukti dalam matematika yang lebih maju, sehingga kedua Turing menghentikan masalah dan teorema Godels dapat dilihat sebagai contoh dari fenomena mendasar yang sama. lihat misalnya:

Teorem penghenti, teorema Cantor (non-isomorfisme suatu himpunan dan set kekuasaannya), dan teorema ketidaklengkapan Goedel adalah semua contoh teorema titik tetap Lawvere, yang mengatakan bahwa untuk setiap kategori tertutup kartesian, jika ada peta epimorfik e: A → (A⇒B) maka setiap f: B → B memiliki titik tetap.

ada juga meditasi panjang tentang tema keterkaitan-diri (intrinsik?) ini dengan referensi-diri dan ketidakpastian dalam buku-buku karya Hofstadter. daerah lain di mana hasil ketidakpastian adalah umum dan pada awalnya agak "mengejutkan" adalah dengan fenomena fraktal. Penampakan silang / signifikansi fenomena tak dapat diputuskan di alam hampir merupakan prinsip fisik yang diakui pada titik ini, pertama kali diamati oleh Wolfram sebagai "prinsip kesetaraan komputasi" .

ay
sumber
area "mengejutkan / terapan" lainnya yang tidak dapat diputuskan: kemiringan aperiodik , akhirnya stabilisasi dalam permainan conway Life ( seluler automata )
vzn
3
Pemahaman saya adalah bahwa bukti bahwa semua masalah ini tidak dapat dipastikan semuanya bermuara pada pengurangan dari masalah penghentian. Apakah itu salah?
templatetypedef
jawabannya pada dasarnya mengakui bahwa (semua hasil ketidakpastian yang diketahui dapat dikurangi menjadi masalah penghentian). pertanyaan Anda hampir diutarakan sebagai dugaan, dan saya tidak mengetahui adanya pengetahuan yang bertentangan dengannya, dan melihat banyak bukti tidak langsung yang mendukungnya. tetapi yang paling dekat dengan bukti formal yang diketahui adalah formulasi titik-tetap dari keraguan (tampaknya tidak ada formulasi formal lain dari "referensi-diri".) Cara lain untuk mengatakan itu semua adalah bahwa Turing kelengkapan dan keraguan adalah dua pandangan. pada dasarnya fenomena yang sama.
vzn