Apakah kompleksitas Kolmogorov fungsi surjektif?

Mari kita perbaiki penyandian mesin-Turing dan mesin-Turing universal, U, yang pada input (T, x) menghasilkan output T apa pun pada input x (mungkin keduanya berjalan selamanya). Tentukan kompleksitas Kolmogorov dari x, K (x), sebagai panjang dari program terpendek, p, sehingga U (p) = x.

Apakah ada N sehingga untuk semua n> N ada x dengan K (x) = n?

Ucapan. Jika kita mendefinisikan mesin Turing universal dengan cara yang berbeda, jawabannya bisa negatif. Sebagai contoh, perhatikan U yang pada input (T, x) mensimulasikan T pada x jika panjang (T, x) dapat dibagi dengan 100, dan jika tidak melakukan apa-apa. Satu dapat memodifikasi contoh ini dalam beberapa cara untuk mendapatkan contoh tandingan untuk definisi yang berbeda dari mesin Turing universal.

Hanya komentar yang diperluas tanpa wawasan mendalam: mungkin Anda dapat menyontek pada penyandian mesin Turing, dan membuat penyandian buatan yang mengarah pada kompleksitas Kolmogorov yang bersifat surjektif:

• $0$ mewakili mesin Turing yang menghasilkan (1 state TM);$0$
• p + 1 p p + $0p$ mewakili mesin Turing yang menghasilkan (angka yang diwakili oleh string biner plus satu); itu hanyalah sebuah versi "zip" implisit dari TM yang dapat memutuskan yang menghasilkan ;$p+1$$p$$p+1$
• p + 1 0 0 $1p$ mewakili mesin Turing dalam enumerasi standar (enumerasi dapat melewati TM yang sudah disertakan dengan dan ).$p+1$$0$$0p$

TM universal yang sesuai pada input memeriksa apa nilai , jika maka hanya output , jika tidak mensimulasikan TM ( ketika adalah string kosong); perhatikan bahwa menanamkan input.b 0 x + 1 M x + 1 M 0 x M x + $bx$$b$$0$$x+1$$M_{x+1}$$M_0$$x$$M_{x+1}$

Untuk semua string , ; dan untuk semua ada string panjang tetapi hanya ada program dengan panjang yang dapat direpresentasikan menggunakan pengkodean ; dan hanya program dengan panjang yang dapat direpresentasikan menggunakan pengodean ; jadi setidaknya string dengan panjang tidak dapat diwakili dengan program panjang ; tapi pasti bisa diwakili dengan program1 ≤ K ( x ) ≤ | x | + 1 n ≥ 1 2 n n 2 n - 1 - 1 < n 1 p 2 n - 1 n 1 p x ′ n 1 p ≤ n 0 x ′ n + 1 1 p n + $x$$1 \leq K(x) \leq |x|+1$$n \geq 1$$2^{n}$$n$$2^{n-1}-1$$< n$$1p$$2^{n}-1$$n$$1p$$x'$$n$$1p$$\leq n$$0x'$dengan panjang (kami tidak khawatir jika ada juga program dengan panjang yang sama yang menghasilkannya).$n+1$$1p$$n+1$

Kita dapat menyimpulkan bahwa untuk semua , ada string sedemikian rupa sehingga (jadi K khusus ini bersifat perkiraan).x ′ , | x ′ | = n K ( x ′ ) = n + $n > 1$$x', |x'|=n$$K(x') = n+1$