Masalah sederhana yang sifat keputusasaannya tidak diketahui

Saya sedang mempersiapkan ceramah yang ditujukan untuk jurusan matematika sarjana, dan sebagai bagian dari itu, saya sedang mempertimbangkan untuk membahas konsep decidability. Saya ingin memberikan contoh masalah yang saat ini tidak kita ketahui tidak dapat ditentukan atau tidak dapat ditentukan. Ada banyak masalah seperti itu, tetapi sejauh ini tidak ada yang tampak sebagai contoh yang bagus.

Apa masalah sederhana-untuk-menggambarkan yang kesopanannya terbuka?

Masalah Matriks Kematian untuk matriks 2x2. Yaitu, diberi daftar terbatas matriks bilangan bulat 2x2 M ₁ , ..., _Mk , dapatkah M _i dikalikan dalam urutan apa pun (dengan banyak pengulangan sewenang-wenang) untuk menghasilkan semua-0 matriks?

(Kasus 3x3 diketahui tidak dapat diputuskan. Kasus 1x1, tentu saja, dapat ditentukan.)

UPDATE: Masalah yang saya sebutkan di sini sekarang diketahui tidak dapat dipastikan! http://arxiv.org/abs/1605.05274 Selain itu, makalah ini terinspirasi oleh membaca jawaban ini. :)

Pemrogram dalam audiens mayor matematika Anda mungkin terkejut mengetahui bahwa pertanyaan "apakah tipe ini secara implisit dapat dikonversi ke tipe itu?" tidak diketahui dapat dipilih dalam Java 5, C # 4 dan Scala 2.

Untuk detail lebih lanjut, lihat makalah Andrew Kennedy dan Benjamin Pierce "Tentang Decidability of Nominal Subtyping with Variance" . Makalah ini memberikan beberapa contoh pembatasan tambahan untuk sistem jenis bahasa-bahasa ini, di mana subtyping nominal diketahui dapat ditentukan atau diketahui tidak dapat diputuskan.

Menariknya, makalah ini ditulis jauh sebelum kovarians generik dan contravariance ditambahkan ke C #, tetapi penulis dengan benar mengantisipasi arah bahasa yang dituju. (Ini tidak mengejutkan; penulis merancang dukungan yang mendasari varian di CLR yang saya manfaatkan ketika menambahkan varian ke C #! Mereka melakukan angkat berat.)

Masalah kesepuluh Hilbert atas rasional: "Apakah persamaan polinomial ini punya solusi rasional?"

Masalah diberikan perulangan linier bersama dengan nilai awalnya, apakah itu mengambil nilai 0?

Dua referensi:

http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/

http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf

Masalah sederhana yang decidability-nya tidak diketahui adalah sebagai berikut (saya pikir itu masih terbuka):

Catur tak terbatas :

Masukan : Daftar terbatas buah catur dan posisi awal mereka pada papan catur; Pertanyaan : Bisakah White memaksa sobat?$Z \times Z$

Jika kita menambahkan batasan bahwa White harus kawin dalam gerakan ( n adalah bagian dari input), maka itu menjadi dapat ditentukan: lihat Dan Brumleve, Joel David Hamkins, dan Philipp Schlicht, Masalah pasangan dalam catur tak terbatas dapat diatasi. .$n$$n$

Masalah sederhana lainnya adalah perilaku semut Langton pada konfigurasi awal yang terbatas.

Perilaku semut Langton dengan dukungan terbatas :

Kotak di pesawat berwarna beragam baik hitam atau putih. Kami secara sewenang-wenang mengidentifikasi satu kotak sebagai "semut". Semut dapat melakukan perjalanan dalam salah satu dari empat arah mata angin pada setiap langkah yang diambilnya. Semut bergerak menurut aturan di bawah ini:

• Di kotak putih, putar 90 ° ke kanan, balikkan warna kotak, maju satu unit
• Di kotak hitam, belok kiri 90 °, balikkan warna kotak, maju satu unit

Input : konfigurasi terbatas (hitam / putih) dari pesawat dan posisi semut;
Pertanyaan : Apakah semut selalu berakhir membangun "jalan raya" tak terbatas berulang?

Untuk dukungan tanpa batas, masalahnya tidak dapat dipastikan, lihat: A. Gajardo, A. Moreira dan E. Goles, Kompleksitas semut Langton

Masalah Collatz adalah masalah sederhana untuk dijelaskan yang keputusasaannya terbuka. Ini melibatkan pengulangan sederhana operasi aritmatika dasar.

$f(n)=\mathsf{\{}$ $n/2$$3n+1$

$n_0$

Menariknya, generalisasi masalah Collatz terbukti tidak dapat diputuskan.

Referensi:

1- MASALAH YANG TIDAK TERPUTUS: SAMPLER , BJORN POONEN

2- Weisstein, Eric W. "Masalah Collatz." Dari MathWorld - Sumber Daya Web Wolfram.

3- Masalah 3X + 1: Suatu Tinjauan , Jeffrey C. Lagarias

Tidak diketahui apakah dapat memutuskan apakah bentuk yang diberikan dapat membentuk bidang atau tidak .

Desidabilitas penahanan query konjungtif telah terbuka selama lebih dari dua puluh tahun. Memecahkan ini akan menjadi terobosan dalam teori database.

$Q_1$$Q_2$$Q_1$$I$$Q_2$$I$

Dalam pertanyaan konjungtif, seseorang menggunakan DAN untuk menghubungkan bersama predikat yang dikuantifikasi secara eksistensial. Dalam istilah SQL, kueri konjungtif adalah kueri SELECT-FROM-WHERE menggunakan "=" dan "AND" tetapi tidak ada subquery atau agregasi. Ini mungkin jenis yang paling umum dari permintaan basis data, dan termasuk sebagian besar permintaan mesin pencari.

$I$$Q_1$$Q_2$

$\ne$

$(N,+,\times)$$(N,+,\times)$

Untuk petunjuk ke literatur yang luas dan perawatan yang ketat, lihat kertas ToDS (di media cetak) oleh beberapa orang.

$Q$$R$$Q$$Q \text{ AND } R$$Q$

Masalah Korespondensi Post dengan jumlah ubin tetap antara 3 dan 6.

Walaupun tidak terlalu sederhana untuk dijelaskan, itu memang memiliki deskripsi yang sangat "lucu", dan saya merasa cocok untuk pembicaraan tingkat intuisi.

Masalah Ketinggian-bintang umum: "Berapa banyak sarang bintang-bintang Kleene yang saya perlukan untuk mewakili bahasa reguler ini, dengan ekspresi reguler dengan komplementasi yang diizinkan?"

Kami bahkan tidak tahu apakah algoritme yang selalu mengembalikan 1 (kecuali 0 untuk bahasa bebas bintang, yang merupakan kasus yang dapat ditentukan) benar.

Masalah dari Teori Automata.

$D$

$x$$D$$x$$x$$L(D) \cap Primes$

Komentar: Saya awalnya mendengar masalah ini dari jawaban stackexchange oleh Jeffrey Shallit. Jika Anda mengetahui referensi untuk itu, beri tahu saya. Terima kasih!

Posting terkait:

(1) Apakah ada masalah terbuka yang tersisa tentang DFA?

(2) https://cs.stackexchange.com/questions/48084/determining-if-infinite-binary-language-dfas-contain-at-least-1-prime

Pekerjaan Terkait: https://cs.uwaterloo.ca/~shallit/Papers/br10.pdf

"Elemen Minimal untuk Bilangan Prime" oleh C. Bright, R. Devillers, dan J. Shallit

Peta berulang pada interval (deskripsi dari sini ):

(sangat terkait dengan masalah yang diajukan oleh Magnus Find)

$F$$x$$x$$x$$F(x)$$F(F(x))$$F$$x$$F$

$F$$x$$y$$x$$y$

$F$

$F$$x$$y$$x$$F$

Referensi: Asarin 2011 .

tampaknya ada cara / sudut yang cukup alami untuk mempelajari pertanyaan ini yang digunakan dalam setidaknya 3 makalah sebagai berikut.

$TM(k,l)$$k$$l$$k,l$$k,l$

hasilnya dapat ditampilkan pada kotak seperti pada beberapa referensi berikut. juga di daerah perantara sebenarnya diketahui bahwa beberapa mesin (tidak terselesaikan) mampu mensimulasikan dugaan Collatz untuk beberapa input.

oleh karena itu jelas ada "titik transisi" seperti fenomena yang beroperasi di sini tetapi tidak dalam wilayah yang dapat dihitung tetapi dalam pengertian yang tidak biasa antara dapat dihitung dan tidak dapat dihitung.

• Mesin Turing kecil dan kompetisi berang-berang sibuk yang digeneralisasi Michel

• Kompleksitas mesin Turing universal kecil: survei Woods, Neary

• Pada batas solvabilitas dan unsolvabilitas dalam sistem tag. Hasil Teoritis dan Eksperimental De Mol

$2^8$

juga sebagai contoh "nyaris celaka", atau "pertanyaan terbuka yang relatif baru diselesaikan sebagai TM selesai", mesin Wolfram 2,3 terbukti universal pada tahun 2007 dengan hadiah $ 25K . kontes diumumkan pada Mei 2007 dan kontes mengumumkan pemenang Smith pada Oktober 2007 .

ada cara yang cukup alami untuk memetakan sebagian besar masalah terbuka ke pertanyaan (tidak) kepastian. kebanyakan masalah terbuka umumnya tidak diketahui dapat dibuktikan atau tidak dapat dibuktikan.

di web ada beberapa kebingungan informal tentang ketidakpastian masalah P vs NP , yang bukan semata-mata masalah keputusan, oleh karena itu untuk berbicara tentang keraguannya itu secara teknis tidak benar. tetapi di sisi lain tampaknya ada hubungan dekat / alami antara ketidakpastian dan provabilitas sebagai berikut.

misalnya pertimbangkan

$L$$x$$O(n^x)$

apakah bahasa ini dapat dipilih? itu adalah pertanyaan tentang bahasa dengan decidability terbuka yang pada dasarnya terkait erat (bahkan, hampir identik) dengan masalah P vs NP dan provabilitas yang melekat (tidak?).

Sedangkan untuk P vs NP sebagai "sederhana untuk digambarkan", itu hanya memerlukan konsep TMs , notasi runtime Big , nondeterminisme yang cukup sederhana (beberapa konsep TCS yang paling dasar) dan diajarkan di tingkat sarjana atau yang berbakat siswa sekolah menengah bisa mengerti.

sebenarnya NP vs P / Poly juga terbuka, dan dapat dipetakan ke pertanyaan terbuka tentang desidabilitas dengan cara yang sama, dan ini dapat dinyatakan sebagai masalah yang cukup sederhana tentang pertumbuhan sirkuit minimal (monoton?) untuk mengenali NP lengkap masalah (misalnya klik).