Bukti untuk kompleksitas Kolmogorov tidak dapat dihitung menggunakan reduksi

Saya mencari bukti bahwa kompleksitas Kolmogorov tidak dapat dihitung menggunakan pengurangan dari masalah lain yang tidak dapat dihitung. Bukti umum adalah formalisasi paradoks Berry daripada reduksi, tetapi harus ada bukti dengan mengurangi dari sesuatu seperti Masalah Putus, atau Masalah Korespondensi Post.

Anda dapat menemukan dua bukti berbeda di:

Gregory J. Chaitin, Asat Arslanov, Cristian Calude: Kompleksitas ukuran Program Menghitung Masalah yang Terputus. Buletin EATCS 57 (1995)

Dalam Li, Ming, Vitányi, Paul MB; Pengantar Kompleksitas Kolmogorov dan Penerapannya disajikan sebagai latihan (dengan petunjuk tentang bagaimana menyelesaikannya yang dikreditkan ke P. Gács oleh W. Gasarch dalam komunikasi pribadi 13 Feb 1992).

** Saya memutuskan untuk menerbitkan versi panjangnya di blog saya .

Ini adalah pertanyaan yang menyenangkan untuk dipikirkan. Seperti dijelaskan dalam jawaban lain dan komentar di bawah ini, ada pengurangan Turing dari masalah Menghentikan ke komputasi kompleksitas Kolmogorov, tetapi terutama tidak ada pengurangan banyak-satu, setidaknya untuk satu definisi 'komputasi kompleksitas Kolmogorov'.

Mari kita secara resmi mendefinisikan apa yang kita bicarakan. Misalkan menunjukkan bahasa standar TM yang berhenti ketika diberikan deskripsi tentang diri mereka sebagai input. Mari K O masing menunjukkan { ⟨ x , k ⟩ | x  memiliki kompleksitas Kolmogorov persis  k } .$HALT$$KO$$\{ \langle x,k \rangle \mid x \text{ has Kolmogorov complexity exactly } k \}$

$HALT \le KO$$f: \{0,1\}^* \rightarrow \{0,1\}^*$$HALT$$f$$f(HALT)$

$f(HALT)$$\langle x,k\rangle$$x$$k$$k$$f(HALT)$$k$$f(HALT)$

$HALT$$f(HALT)$$k$$f(HALT)$$\langle x,k\rangle$$k$$M$$k$$\langle x,k \rangle \in f(HALT)$

$M'$$|M'|$$M$$|M'|+1$$\langle x, |M'|+1\rangle \in f(HALT)$$x$

$x$$M'$$|M'|$$\langle x, |M'|+1\rangle \in f(HALT)$

$k$$k$