Kompleksitas Kolmogorov

Gagasan tentang kompleksitas Kolmogorov dapat digunakan untuk menyatakan dan membuktikan kemustahilan sama dengan argumen diagonal Cantor, Teorema ketidaklengkapan Gödel, dan masalah terputus Turing.
Secara khusus, untuk hampir setiap objek, tidaklah mungkin untuk menghitung bahkan batasan yang lebih rendah untuk kompleksitas Kolmogorov-nya (Chaitin 1964), apalagi nilai pastinya.