Kesetaraan definisi Kolmogorov-Kompleksitas

Ada banyak cara untuk mendefinisikan Kolmogorov-Complexity , dan biasanya, semua definisi ini setara dengan konstanta aditif. Itu adalah jika dan adalah fungsi kompleksitas kolmogorov (didefinisikan melalui berbagai bahasa atau model), maka terdapat konstanta sedemikian rupa sehingga untuk setiap string , . Saya percaya ini karena untuk setiap fungsi kompleksitas Kolmogorov dan untuk setiap menyatakan bahwa , untuk beberapa konstanta .K 2 c x | K 1 ( x ) - K 2 ( x ) | < c K x K ( x ) ≤ | x | + c $K_1$$K_2$$c$$x$$|K_1(x) - K_2(x)| < c$$K$$x$$K(x) \le |x| +c$$c$

Saya tertarik pada definisi berikut untuk , berdasarkan pada mesin Turing$K$

1. jumlah status : Tentukan sebagai jumlah minimal sedemikian sehingga TM dengan menyatakan output pada string kosong.q q $K_1(x)$$q$$q$$x$
2. $K_2(x)$$x$$M$$\langle M \rangle$M $K_2(x) = \min |\langle M \rangle|$$M$$x$

Apakah dan setara? Apa hubungan di antara mereka, dan yang mana yang lebih baik memahami konsep kompleksitas Kolmogorov, jika mereka tidak setara.K $K_1$$K_2$

Yang terutama mengganggu saya adalah laju meningkat dengan , yang tampaknya tidak super-linear (atau paling tidak linear dengan konstanta sedemikian rupa sehingga , daripada | x | + c ). Pertimbangkan TM paling sederhana yang menghasilkan x - yang hanya menyandikan x sebagai bagian dari fungsi status dan transisinya. langsung melihat bahwa K_1 (x) \ le | x | +1 . Namun pengkodean mesin yang sama jauh lebih besar, dan batas sepele yang saya dapatkan adalah K_2 (x) \ le | x | \ log | x | . x C > 1 K 2 < C | x | | x | + c x x K 1 ( x ) ≤ | x | + 1 K 2 ( x ) ≤ | x | log | x $K_2$$x$$C>1$$K_2 < C|x|$$|x|+c$$x$$x$$K_1(x) \le |x|+1$$K_2(x) \le |x|\log |x|$

Saya minta maaf sebelumnya karena saya memberikan terlalu banyak detail, tapi saya akan bertentangan dengan orang.

Tentang $K(x)≤K'(x)+c$

Fakta bahwa biasanya berasal dari penerjemah bahasa deskripsi # 2 ke dalam bahasa deskripsi # 1 dan bukan dari terjemahan dari program # 2 ke dalam program # 1.$K_1(x)≤K_2(x)+c$

Misalnya dan Anda mendapatkan ketimpangan ini sesederhana ini:$K_\mathtt{C}(x)≤K_\mathtt{Python}(x)+c_\mathtt{py2c}$

void py_run(char * s) {
    // code of your Python interpreter
}

int main(void) {
    py_run("Put here your Python program of size Kpython(x)");
}

Maka konstanta Anda akan menjadi sesuatu seperti 528 + 490240688 di mana 528 adalah jumlah bit untuk kode ini dan 490240688 bit adalah ukuran penerjemah resmi Python yang ditulis dalam C. Tentu saja Anda hanya perlu menafsirkan apa yang mungkin dalam bahasa deskripsi Anda untuk Python sehingga Anda dapat melakukan lebih baik dari 69 MB :-)$c_\mathtt{py2c}$$528+490240688$$528$$490240688$

Yang penting adalah Anda dapat menulis program Python Anda secara linear dalam kode C. Misalnya, bahasa tempat Anda harus meletakkan "BANANA" di antara setiap karakter bukanlah program deskripsi yang sangat baik dan properti tersebut kemudian salah. (Tetapi jika bahasa deskripsi mengizinkan Anda untuk menulis data dalam file terpisah atau dalam blok, masalah ini hilang)

Mengapa cacat$K_1(x)=q$

Masalah dengan definisi adalah bahwa Anda mungkin memerlukan lebih dari q bit untuk menggambarkan mesin Turing dengan status q karena Anda perlu menyandikan transisi.$K_1$$q$$q$

Jadi tidak ada dan K 2 yang mungkin tidak setara, tapi itu terutama kesalahan K 1 . Saya pikir kita dapat membuktikan bahwa untuk semua a > 0 ada c a sehingga K 1 ( x ) ≤ a | x | + c a . Tentu saja setiap satu < 1 sudah cukup untuk menyangkal fakta bahwa K 1 bukan fungsi valid, karena akan berarti bahwa kita dapat mengkodekan lebih semua 2 n kemungkinan string panjang$K_1$$K_2$$K_1$$a>0$$c_a$$K_1(x)≤a|x|+c_a$$a<1$$K_1$$2^n$ ke dalam sebuah n + c a bit.$n$$an+c_a$

Tapi ukurannya sangat terikat ketika membangun mesin Turing. Idenya adalah bahwa dalam blok menyatakan ada b 2 b cara untuk menemukan transisi untuk setiap negara dan itu lebih baik daripada 2 b cara biasa Anda dapat mengisi b bit. Kemudian Anda dapat menyimpan di setiap blok log 2 b bit informasi. (bukan 2 log 2 b karena Anda harus masuk dan keluar blok satu atau lain cara)$b$$b^{2b}$$2^b$$b$$\log_2 b$$2\log_2 b$

Jadi ya ... Dengan balok ukuran Anda mungkin bisa membuktikan K 1 ( x ) ≤ a | x | + c a . Tapi saya sudah menulis terlalu banyak tentang mengapa jumlah negara bukan fungsi kompleksitas Kolmogorov yang valid. Jika Anda ingin saya menguraikan, saya akan.$2^{1/a}$$K_1(x)≤a|x|+c_a$

Sekarang tentang $K_2$

Bahasa deskriptif naif berkorespondensi kira-kira dengan (yaitu log 2 q untuk setiap negara bagian berikutnya dan rincian tentang menulis dan penghentian).$K_2(x)=q\cdot 2 \cdot (\log_2 q + 2)$$\log_2q$

Seperti yang tampaknya, saya yakin bahwa cara yang lebih baik / curang adalah mengotorisasi untuk menyandikan "data" ke mesin Turing, mungkin dengan menambahkan tag biner dalam bahasa deskripsi yang mengatakan apakah suatu negara adalah keadaan data ( yang hanya menulis sedikit dan pergi ke negara bagian berikutnya) atau jika melakukan sesuatu yang lain. Dengan begitu Anda bisa menyimpan satu bit Anda dalam sedikit bahasa deskriptif Anda.$x$

Namun jika Anda menyimpan sama, Anda bisa menggunakan teknik yang sama yang saya gunakan di bagian sebelumnya untuk menghemat beberapa bit, tetapi saya sepertinya terjebak di K 2 ( x ) ≤ a | x | log | x | + c (untuk a > 0 ) .. mungkin kurang dari log | x | , bahkan, tetapi mendapatkan O ( | x | ) tampaknya sulit. (Dan saya berharap seharusnya | x | , bahkan bukan O ( $K_2$$K_2(x)≤a|x|\log|x|+c$$a>0$$\log|x|$$O(|x|)$$|x|$ .)$O(|x|)$