כל מה שרצית לדעת על משפט האי-שלמות של צ'ייטין:
משפט האי-שלמות של צ'ייטין הוא משפט הקובע שבכל תורה עקבית עשירה מספיק, לא ניתן להוכיח טענות מסוימות לגבי סיבוכיות קולמוגורוב, למרות שהן נכונות.
המשפט פורסם על ידי המתמטיקאי ומדען המחשב האמריקאי גרגורי צ'ייטין בשנת 1971.
ביתר פירוט, המשפט קובע שלכל תורה עקבית, ואפקטיבית שמסוגלת לתאר סיבוכיות קולמוגורוב קיים קבוע , כך שלכל n טבעי, לא ניתן להוכיח את הטענה "סיבוכיות קולמוגורוב של n גדולה מ-L", זאת על אף שיש מספרים טבעיים שהטענה נכונה לגביהם.
מכיוון שהמשפט מראה שיש טענות נכונות שאי אפשר להוכיחן, אז בהכרח התורה אינה שלמה.
לכן, למרבית התורות, משפט האי-שלמות הראשון של גדל מתקבל כמסקנה של משפט האי-שלמות של צ'ייטין (המשפט של גדל דורש תנאים מוחלשים במעט לגבי התורה ולכן תקף גם לתורות סטנדרטיות פחות).
בניגוד להוכחת המשפט של גדל, שדומה לפרדוקס השקרן, הוכחת המשפט של צ'ייטין עושה שימוש בפרדוקס של ברי.
ההוכחה מראה שאם המשפט אינו נכון, אז מקבלים סתירה בדמות הפרדוקס של ברי.