Ketidakmungkinan dalam Komputasi dan Kompleksitas: selalu pada akhirnya karena argumen diagonal?

Dalam Computability, jika kita ingin membuktikan bahwa masalah tidak rekursif atau tidak dihitung secara rekursif, kita dapat menggunakan misalnya pengurangan dari masalah non-rekursif atau non-re lainnya, teorema Rice, teorema Rice-Shapiro, dll. Teknik-teknik ini bekerja berkat , atau secara langsung didasarkan pada, adanya beberapa argumen diagonal (yaitu beberapa program berperilaku sebaliknya sebagai program inputnya , jadi adalah kontradiktif). Dalam Kompleksitas, jika kami ingin membuktikan bahwa beberapa masalah tidak dapat dihitung dalam beberapa waktu (terlepas dari klaim yang tidak terbukti seperti misalnya ), kami menggunakan argumen yang, pada akhirnya, didasarkan pada beberapa argumen diagonal (misalnya Hierarki Waktu teorema membuktikanM ′ M = M $M$$M'$$M = M'$E X P T I M $P \neq NP$$EXPTIME$Masalah -complete tidak dalam , tetapi teorema itu juga dibuktikan dengan menggunakan argumen diagonal).$P$

Jadi pertanyaan saya adalah sebagai berikut. Apakah semua ketidakmungkinan penting menghasilkan Computability and Complexity (ketidakmungkinan aktual, bukan ketidakmungkinan sampai beberapa hasil yang tidak terbukti) pada akhirnya karena beberapa argumen diagonal? Yaitu, apakah semua "pengetahuan ketidakmungkinan" penting kita dalam Komputasi dan Kompleksitas berasal dari fakta bahwa program cukup kuat untuk menjalankan program?

Satu-satunya hasil ketidakmungkinan penting yang muncul dalam pikiran saya yang pada akhirnya bukan karena argumen diagonal adalah bahwa fungsi Ackermann bukan rekursif primitif. Apakah saya kehilangan contoh tandingan penting lainnya dari "aturan" yang tampak ini?

EDIT (18 Nov): Maaf untuk menyiratkan bahwa pertanyaan saya terutama berfokus pada argumen diagonal itu sendiri, tetapi saya lebih tertarik pada semua argumen yang mengandalkan referensi diri dari program (termasuk argumen diagonal, Berry paradox, dll). Untuk bahasa yang lebih sederhana (mis. Reguler atau bebas konteks), kami memiliki argumen ketidakmungkinan "struktural" berdasarkan pada bagaimana bahasa ini dikonstruksi (misalnya memompa lemma). Namun, untuk bahasa rekursif atau re, sebagian besar hasil ketidakmungkinan sangat bergantung pada referensi diri program. Ini yang saya maksud.

Batas bawah pada model perhitungan yang tidak seragam, seperti rumus dan sirkuit boolean, terbukti menggunakan argumen kombinatorial. Beberapa contoh adalah metode Krapchenko menggunakan ukuran kompleksitas formal, metode pendekatan Razborov untuk sirkuit monoton, metode pembatasan acak, termasuk pembatasan acak + lemma switching, dan batas bawah yang lebih dalam menggunakan kompleksitas komunikasi melalui permainan Karchmer-Wigderson. Anda dapat menemukan catatan kuliah tentang materi ini oleh Sudan , Kopparty , Buss , Zwick , antara lain.

Model perbandingan-batas bawah standar untuk penyortiran, dan kebanyakan model probe sel batas bawah untuk struktur data, tidak bersyarat (untuk komputasi dalam model tetapi Anda bisa mengatakan hal yang sama tentang mesin batas bawah Turing mesin) dan bergantung pada teori informasi daripada diagonalisasi.

Alat yang dapat digunakan untuk membuktikan hasil negatif / ketidakmungkinan adalah metode inkompresibilitas :

Teorema (Incompressibility Theorem) Misalkan menjadi bilangan bulat positif. Untuk setiap y tetap , setiap himpunan terbatas A dari kardinalitas m memiliki setidaknya m ( 1 - 2 - c ) + 1 elemen X dengan C ( x ∣ y ) ≥ log m - $c$$y$$A$$m$$m(1-2^{-c})+1$$X$$C(x \mid y) \geq \log m - c$

Beberapa aplikasi terkenal adalah: satu mesin pita Turing membutuhkan langkah untuk memutuskan { w w R } ; DFA tidak dapat mengenali sebuah n b n ; ketidakmungkinan hanya ada banyak bilangan prima (dan memperkirakan ukuran bilangan prima dengan benar dalam faktor log n); ....$O(n^2)$$\{ ww^R\}$$a^n b^n$

Pada akhirnya teorema di atas bergantung pada Prinsip Pigeon yang memiliki beberapa aplikasi langsung yang bagus; sebagai contoh:

Teorema : jika kita mewarnai titik-titik pada bidang merah atau biru. Kemudian untuk jarak apa pun , kita dapat menemukan dua titik pada jarak d dari satu sama lain yang memiliki warna yang sama.$d > 0$$d$

Bukti : Pilih segitiga sama sisi dengan sisi yang sama dengan pada bidang nyata. Ini memiliki tiga simpul, sehingga dengan prinsip lubang pigeon, keduanya harus memiliki warna yang sama, dan mereka berada pada jarak d dari satu sama lain oleh konstruksi.$d$$d$

Sebenarnya, masalah penghentian dapat dibuktikan tanpa menggunakan diagonalisasi. (Dan setiap teorema ZFC yang valid memiliki bukti ZFC yang menggunakan diagonalisasi ... pikirkanlah.)

Buktinya menggunakan paradoks Berry, dan hasil sebagai berikut:

Indeks semua mesin Turing dengan cara yang masuk akal. Asumsikan demi kontradiksi bahwa masalah penghentian dapat diselesaikan. Kemudian pertimbangkan algoritma ini:

f (N) mengembalikan mesin Turing paling terindeks X st X (X) tidak berhenti dan X bukan output dari setiap mesin Turing M dan input I di bawah karakter N (yaitu, M (I) menghasilkan X -> | M | + | I |> = N).

Sekarang, kita memilih Nf f (N) yang cukup besar harus mengembalikan deskripsi X yang dideskripsikan dengan perhitungan f (N). Jika f dapat dihitung, maka M = f dan I = N. Sebagai contoh, kita dapat membiarkan N = satu googol (10 ^ 100).

Ini menunjukkan bahwa f (N) bukan fungsi total, karena untuk f (10 ^ 100), tidak ada output yang memuaskan. Ini bertentangan dengan asumsi bahwa masalah penghentian dapat diselesaikan. Pertimbangkan pseudocode berikut (yang jauh lebih sedikit dari 10 ^ 100 karakter ketika diperluas ke kode sumber yang benar dalam C ++ atau bahkan ditulis sebagai mesin Turing) untuk f:

f (N)

{

untuk (int i = 1;; i ++)

{

  if (simulate DoesHalt(UTM(i,i)) == false)

  {

         (simulate all machines and inputs M(I) with |M|+|I|<N)

         if all such inputs do not output i

                 return i;

  }

}

}

Jelas, f berhenti pada semua input dan bekerja dengan benar dengan asumsi bahwa penghentian masalah dapat diselesaikan. Dengan hal di atas, kami memiliki masalah penghentian tidak dapat diselesaikan.

Bukti ini tidak menggunakan segala bentuk diagonalisasi. Memang, Anda harus melihat pertanyaan saya:

Apakah salah satu definisi kata paradoks, "sesuatu yang dapat digunakan untuk membuktikan masalah yang terputus-putus?"

... untuk beberapa diskusi tentang fakta bahwa banyak paradoks dapat digunakan sebagai pengganti paradoks pembohong atau paradoks Russell untuk membuktikan bahwa masalah penghentian tidak dapat diselesaikan. Beberapa paradoks non-diagonal-argumen ini termasuk Paradox Gantung Tak Terduga dan (seperti yang baru saja dijelaskan) Berry Paradox.