Membandingkan kompleksitas teori Kolmogorov

Ketidaklengkapan Chaitin teorema mengatakan teori tidak cukup kuat aritmatika dapat membuktikan $K(s) > L$ mana adalah kompleksitas Kolmogorov string dan adalah konstan cukup besar. adalah cukup besar jika lebih besar dari ukuran dalam bit dari mesin pemeriksaan bukti (PCM). Sebuah PCM teori mengambil string disandikan sebagai integer sebagai masukan dan output 1 jika string adalah bukti yang sah dalam bahasa .$K(s)$$s$$L$$L$$T$$T$

Asumsikan bahwa $L(T) > |PCM_T|$teori $T$ adalah batas atas untuk kompleksitas $T$ . Pertimbangkan hierarki teori berikut: Biarkan teori dasar menjadi aritmatika Robinson ( $Q$ ). Menambah $Q$ dengan aksioma induksi terikat polinomial yang semakin kuat. Biarkan $Q^*$ menjadi teori teorema yang dibuktikan dengan $Q$ dan semua aksioma induksi terbatas ini. Asumsikan kita dapat mendefinisikan $L(Q)$ dan $L({Q^*})$ dengan mendefinisikan PCM untuk setiap teori.

Saya ingin mempertimbangkan EPCM untuk $Q^*$ . EPCM ini mengambil string sebagai input seperti halnya ECM dan memiliki input kedua yang mendefinisikan pangkat dan level dari sub-teori $Q^*$ . Jika string input adalah bukti yang valid di $Q^*$ EPCM kemudian melalui langkah-langkah bukti untuk menentukan peringkat tertinggi dan level induksi yang digunakan. EPCM ini kemudian menulis 1 jika kalimat input adalah bukti yang valid dalam sub-teori tertentu dari $Q^*$ .

Apakah pemeriksa bukti yang ditingkatkan yang saya uraikan layak? Jika demikian, apakah ukuran EPCM ini menjadi batas atas tidak hanya untuk kompleksitas , tetapi juga batas atas pada kompleksitas sub-teori Q ∗ ?$Q^*$$Q^*$

Apakah masuk akal untuk mengatakan ada batas atas konstan pada kompleksitas dan semua sub-teorinya?$Q^*$

---

Pertanyaan ini diilhami oleh bukti kegagalan Nelson tentang ketidakkonsistenan aritmatika. Saya tidak menunjukkan ini sebelumnya karena beberapa orang menemukan bukti itu mengganggu. Motivasi saya adalah mengajukan pertanyaan yang menarik. CSTheory tampaknya menjadi forum yang tepat untuk pertanyaan ini. Kompleksitas dan semua sub-teorinya dibatasi oleh konstanta atau tidak terikat. Salah satu jawaban mengarah ke lebih banyak pertanyaan.$Q^*$

Jika kompleksitas sub-teori tidak terbatas, kita dapat mengajukan pertanyaan seperti apa sub-teori terlemah dari lebih kompleks daripada Q ∗ ? Atau lebih kompleks dari PA dan ZFC? Memikirkan pertanyaan ini telah menunjukkan kepada saya bahwa ada batas parah pada seberapa banyak teori dapat membuktikan tentang kompleksitas string Kolmogorov. Jika Q ∗ konsisten maka tidak ada sub-teorinya yang dapat membuktikan K ( s ) > L ( Q ∗ ) untuk string apa pun. Ini berarti bahkan sub-teori yang sangat kuat tidak dapat membuktikan ada string yang lebih kompleks daripada sub-teori yang jauh lebih lemah di mana teori yang lebih lemah lebih kompleks dari $Q^*$$Q^*$$Q^*$$K(s) > L(Q^*)$ .$Q^*$

Saya akan mencoba dan memberikan jawaban untuk pertanyaan ini, dan mencoba untuk menjernihkan beberapa kebingungan mengenai bentuk pertanyaan yang tepat.

Titik pertama yang saya ingin membuat: dalam laporan Chaitin konstanta memang fungsi dari T . Dalam pengertian absolut , itu adalah monotonik dalam ekspresi T : jika L ( T ) adalah bilangan alami terkecil dimana T ⊬ K ( s ) ≥ L ( T ) untuk setiap string s , maka jika T ′ adalah teori yang konsisten lebih kuat dari T ( T ⊢ φ menyiratkan T $L$$T$$T$$L(T)$

$$T\not\vdash K(s)\geq L(T)$$ $s$$T'$$T$$T\vdash\varphi$ untuk kalimat aritmatika φ ) lalu L ( T ′ ) ≥ L ( T ) . Argumennya sangat sederhana: jika ada s sehingga T ⊢ K ( s ) ≥ L maka T ′ ⊢ K ( s ) ≥ L dengan hipotesis.$T'\vdash\varphi$$\varphi$$L(T')\geq L(T)$$s$$T\vdash K(s)\geq L$$T'\vdash K(s)\geq L$

Namun, ini hanya benar jika adalah konstanta Chaitin absolut . Secara khusus, jika T ' membuktikan C o n ( T ) , maka T ' ⊢ ∃ L ∀ s ⌈ T ⊬ K ( ¯ s ) ≥ ¯ L$L(T)$$T'$$\mathrm{Con}(T)$

$$T'\vdash \exists L\forall s\ \lceil T\not\vdash K(\overline{s})\geq \overline{L}\rceil$$

dengan menginternalisasi argumen Chaitin. Namun , sebuah beton yang$l$

$$T'\vdash\forall s\ \lceil T\not\vdash K(\overline{s})\geq\overline{l}\rceil$$

secara umum tidak akan sama dengan $L(T)$ . Secara khusus mungkin jauh lebih besar, umumnya sebanding dengan ukuran bukti di T $\mathrm{Con}(T)$$T'$ . Hal ini dapat dengan mudah dilihat pada bukti teorema itu sendiri, yang krusial bergantung pada konsistensi .$T$

Jadi sementara dapat membuktikan konsistensi sistem dengan induksi terikat, panjang bukti ini semakin lama semakin dekat dengan Q ∗ dalam ekspresi (salah satu cara untuk memahami teorema ketidaklengkapan adalah bahwa panjangnya menjadi tak terbatas ketika Anda mencapai Q ∗ , dengan demikian ia tidak memiliki bukti konsistensi yang terbatas dalam Q ∗ itu sendiri). Dengan demikian hal yang sama berlaku untuk berbagai batas atas pada L ( T ) s Q ∗ internal yang dapat menggambarkan untuk setiap sub-teori.$Q^*$$Q^*$$Q^*$$Q^*$ $L(T)$$Q^*$

Jadi, inilah jawaban singkat untuk pertanyaan Anda: terikat secara seragam untuk semua sub-teori Q ∗ , tetapi Q ∗ sendiri tidak dapat menunjukkan bahwa ikatan ini berlaku untuk semua sub-teori tersebut. Ini adalah kesalahan krusial yang dibuat Nelson (terkubur di bawah beberapa lapisan formalisme) dan yang ditunjukkan Tao di sini .$L(T)$$Q^*$$Q^*$