סיבוכיות קולמוגורוב – הבדלי גרסאות

לא קיים [[אלגוריתם]] המסוגל [[חישוב (מדעי המחשב)|לחשב]] את סיבוכיות קולמוגורוב לכל מחרוזת שהיא. יתר על כן, ניתן להשתמש בסיבוכיות קולמוגורוב בכדיכדי לבנות טענות ש[[עצמאות (לוגיקה מתמטית)|לא ניתנות להוכחה או הפרכה]] במסגרת [[תורה (לוגיקה מתמטית)|תורה]] מסוימת. דוגמה לתוצאה שכזו היא [[משפט האי-שלמות של צ'ייטין]].