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