משפט האי-שלמות של צ'ייטין

משפט האי-שלמות של צ'ייטין הוא משפט הקובע שבכל תורה עקבית עשירה מספיק, לא ניתן להוכיח טענות מסוימות לגבי סיבוכיות קולמוגורוב, אף על פי שהן נכונות. המשפט פורסם על ידי המתמטיקאי ומדען המחשב האמריקאי גרגורי צ'ייטין בשנת 1971.

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

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

נוסח פורמלי

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

משפט האי-שלמות של צ'ייטין. לכל תורה עקבית ואפקטיבית שמסוגלת לתאר סיבוכיות קולמוגורוב קיים קבוע $L$ (התלוי בתורה ובשפת התכנות) כך שלכל n טבעי לא ניתן להוכיח את הטענה "$L<K(n)$" במסגרת התורה.

יש רק מספר סופי של תוכניות מחשב שקצרות מ-$L$. לכן יש רק מספר סופי של מספרים שמקיימים $L\geq K(n)$, וכמעט כל המספרים מקיימים $L<K(n)$. למרות זאת, משפט האי-שלמות של צ'ייטין קובע שלגבי אף אחד מן המספרים האלה לא ניתן להוכיח באופן ספציפי ש-$L<K(n)$.

הוכחה

תהא $T$ תורה המקיימת את תנאי המשפט. יהי $L$ מספר טבעי גדול מספיק (התנאי המדויק על L ייקבע בהמשך). נניח בשלילה שקיים $n$ כך שקיימת הוכחה לטענה $L<K(n)$. נסדר את כל ההוכחות האפשריות ב-$T$ בסדרה לפי סדר לקסיקוגרפי. נסמן ב-$w$ את ההוכחה הראשונה בסדרה לטענה מהצורה $L<K(n)$. נסמן ב-$m$ את המספר שלגביו $w$ מוכיחה כי $L<K(m)$.

נתאר כעת תוכנית מחשב $M$ שמדפיסה את $m$. $M$ עוברת אחת אחת על כל ההוכחות בסדרה עד שהיא פוגשת הוכחה לטענה מהצורה $L<K(n)$, ואז היא מדפיסה את $n$ (כאן נכנסת הדרישה ש-$T$ אפקטיבית, אחרת לא ניתן לזהות את ההוכחה). לפי ההגדרות שקבענו, $M$ תפגוש $w$ ותדפיס את $m$.

כעת נעריך את האורך של התוכנית $M$. החלק ב-$M$ שמגדיר את המעבר על הסדרה ואת קריאת ההוכחות הוא מאורך קבוע. האורך של החלק שמורה לבדוק האם ההוכחה מוכיחה טענה מהצורה $L<K(n)$ תלוי באורך של הייצוג של $L$. את $L$ ניתן לייצג בשיטה העשרונית בעזרת $\log L$ תווים. לכן האורך של התוכנית $M$ כולה הוא $C+\log L$ כאשר $C$ מספר קבוע כלשהו (שערכו תלוי בשפת תכנות וב-$T$).

ל-$L$ גדול מספיק מתקיים האי-שוויון $C+\log L<L$. מכאן ש-$M$ היא תוכנית מחשב שאורכה קצר מ-$L$ והיא מדפיסה את $m$ ולכן $L>K(m)$. זאת בסתירה ל-$w$ שמוכיחה ש-$L<K(m)$. לכן $T$ לא יכולה להיות עקבית.

מסקנות

בשנת 1943 המתמטיקאי סטפן קליני הוכיח שתורות הכוללות את האריתמטיקה הסטנדרטית מסוגלות לתאר חישוביות. לתורות אלו משפט האי-שלמות של צ'ייטין מוכיח אי-שלמות וגורר את המשפט הראשון של גדל. למקרים האלו קליני כבר הציג הוכחה קצרה במיוחד למשפט של גדל, בהסתמך על אי-כריעות בעיית העצירה.

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

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

קישורים חיצוניים

• Algorithmic Information Theory - Some Recollections
• The Surprise Examination Paradox and the Second Incompleteness Theorem, המאמר של שירה קריצ'מן ורן רז

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

31026673משפט האי-שלמות של צ'ייטין