הפוסט המעניין ביותר שלא ניתן לתאר בכותרת שלו

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

הפרדוקס של ברי נובע מכך שהמשפט הבא לכאורה מתאר מספר, אך למעשה לא יכול לתאר כלום: “המספר הטבעי הקטן ביותר שלא ניתן לתאר בפחות ממאה אותיות”. אם תספרו את מספר האותיות במשפט הזה, תראו כי יש בו פחות מ-100 (אפילו כולל רווחים). אם כן, מה הולך כאן? מצד אחד, המספר שמתואר במשפט הזה לא ניתן לתיאור בפחות ממאה אותיות, ומצד שני זה בדיוק מה שעשינו! פרדוקס!

הבה וננסה לחשוב על כל העניין יותר לעומק. בלי להשתמש במילה “הפניה עצמית”.

כדי לתאר מספרים טבעיים אפשר להשתמש בדרכים רבות. למשל, כדי לתאר את המספר 3 אפשר להגיד “שלוש”. אפשר גם להגיד “אחד ועוד אחד ועוד אחד” או “שמונה חלקי שתיים פחות ארבע חלקי ארבע”. מן הסתם “שלוש” הוא התיאור הכי קומפקטי, אבל לא היחיד. מכיוון שלמרביתם המוחצת של המספרים אין שם מפורש, הדרך היחידה לתאר אותם היא באמצעות מספרים אחרים ופעולות עליהם. כך למשל “גוגול” אמנם מתאר בעזרת מספר קטן של אותיות את \( 10^{100} \), אבל איך אפשר לתאר את \( 10^{137} \)? אין מנוס מלהגיד “עשר בחזקת מאה שלושים ושבע” - שימו לב, גם בתיאור הזה יש פחות מ-100 אותיות, כך שגם \( 10^{137} \) עדיין נחשב למספר שניתן לתאר באמצעות פחות מ-100 אותיות.

האם ניתן לתאר כל מספר טבעי באמצעות פחות מ-100 אותיות? התשובה היא כמובן שלא, והדרך הפשוטה ביותר להראות זאת היא באמצעות שיקולי ספירה - יש 22 אותיות בעברית, ונחשיב גם את רווח בתור תו, ולכן נקבל שיש רק \( 23^{100} \) משפטים שאורכם לכל היותר 100 תווים. חלקם חסרי משמעות לגמרי, כמו “עכגעג”. חלקם בעלי משמעות לא-מספרית, למשל  “הפוסט הזה משעמם נורא”. רק למתי-מעט מתוכם יש משמעות מספרית - אבל גם אם לכולם הייתה משמעות מספרית, הם עדיין היו מתארים רק \( 23^{100} \) מספרים שונים - ויש אינסוף מספרים טבעיים.

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

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

יש שני דברים משונים בהגדרה שלי. ראשית, למה בכלל לדבר על תוכניות מחשב ולא על שפה טבעית? הסיבה לכך היא שכפי שראינו, שפה טבעית יכולה להיות אמביוולנטית ותלויה בקורא. לעומת זאת, תוכנית מחשב (שאינה מבצעת הגרלות ואין בה פקודות לא חוקיות שתוצאתן אינה מוגדרת) היא חד משמעית ותמיד מוציאה את אותו הפלט (או “נתקעת” ולא מוציאה פלט כלל). גם כשמתארים מספר בשפה טבעית, לרוב אנחנו הקוראים מריצים מעין תוכנית מחשב בראש כדי “להבין” מה המספר (כך אנו יודעים ש”שלוש חלקי שלוש” מייצג את המספר 1).

אם כן, מה שנותר להבין הוא מדוע השפה רובי דווקא. התשובה הפשוטה היא שזו השפה האהובה עלי; אך האם אין מספרים שניתן לתאר בשפה אחרת (למשל, ++C) אך לא ברובי?

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

puts 37

(puts היא פקודת ההדפסה הבסיסית של רובי).

מכאן אנו למדים שברובי אפשר לכתוב כל מספר באמצעות תוכנית שהגודל שלה שווה לאורך המספר בייצוג עשרוני, ועוד חמישה תווים (התווים של puts והרווח שאחריו). האם אפשר לשפר? לפעמים כן. קחו את המספר "מיליון, ארבעים ושמונה אלף חמש מאות שבעים ושש". תוכנית אחת עבורו היא זו:

puts 1048576

בתוכנית הזו ישנם 12 תווים. לעומת זאת, הנה תוכנית "טובה יותר":

puts 2**20

שתי כוכביות ברצף מציינות ברובי את אופרטור החזקה - מה שהתוכנית עושה הוא להדפיס את תוצאת החישוב של שתיים בחזקת עשרים - בדיוק המספר 1,048,576. ספירה מהירה תראה שיש רק 10 תווים בתוכנית הזו - כלומר, היא קצרה יותר.

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

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

נעבור לקצת פורמליזם. בהינתן מודל חישובי \( M \) שמחשב פונקציה כלשהי, כלומר בהינתן \( x \) הוא מוציא פלט \( y=M(x) \), אפשר להגדיר פונקציה \( K_M(y) \) באופן הבא:

\( K_M(y)=\min_{n}\left\{\exists x: |x| = n \wedge M(x)=y\right\} \)

במילים: על הקלט y (שהוא מספר טבעי), הפונקציה \( K_M \) מחזירה את האורך הקטן ביותר של x (על x אנו חושבים בתור קוד של תוכנית מחשב, כלומר סדרת תווים) כך ש-M, כשהיא מופעלת על x, מחזירה y.  את הדיון שקיימתי קודם על הקשר בין רובי ו-++C אפשר לסכם באופן הבא: לכל שני מודלים \( M_1,M_2 \) קיים קבוע \( c \) כך שלכל \( y \) מתקיים:

\( K_{M_1}(y)\le K_{M_2}(y)+c \)

במילים אחרות, אולי המודל השני קצת יותר יעיל מהראשון ואת חלק מהמספרים אפשר לתאר בו בצורה יותר קומפקטית, אבל ה"קומפקטיות" הזו היא מגודל קבוע c, ולא מגודל שתלוי בגודל ומורכבות המספר שאנו מנסים לתאר. מכיוון שברוב השאלות ששואלים על סיבוכיות קולמוגורוב הקבוע c הזה אינו חשוב, נהוג לקבוע מודל ספציפי אחד (במקרה שלי, רובי; במקרים אחרים רבים, מכונת טיורינג) ולעבוד רק בו. את הפונקציה של סיבוכיות קולמוגורוב עבור מודל זה מסמנים פשוט בתור K, בלי M שכתוב למטה.

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

ראשית, הקבוצה. במקור דיברנו על 100 אותיות, אבל אפשר היה לדבר על מספר \( n \) כללי של אותיות. אם כן, אגדיר את הקבוצה הבאה: \( A_n=\left\{y: K(y)\le n\right\} \). במילים - קבוצת כל המספרים עם סיבוכיות קולמוגורוב של לכל היותר n - "קבוצת כל המספרים שאפשר לתאר באמצעות תוכנית מחשב עם לכל היותר n תווים".

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

מה הבעיה? שלא ברור לנו איך אפשר לחשב את K. הגישה הנאיבית אומרת "מה הבעיה? בהינתן y שעבורו אתה רוצה לחשב את \( K(y) \), תריץ את כל תוכניות המחשב ברובי מאורך 1 ותראה מה הן מחזירות: אם אחת מהן החזירה את \( y \), הדפס 1; אחרת, תריץ את כל התוכניות מאורך 2 וכן הלאה וכן הלאה. הבעיה היא שלא כל תוכניות המחשב הללו עוצרות בכלל; בפרט, אם התוכנית שלי, זו שמבצעת את הסימולציה הזו, מתישהו מנסה להריץ את עצמה, היא עצמה תריץ את עצמה שוב, ושוב, ושוב... ולא תעצור אף פעם.

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

מה שאראה כעת הוא שאם יש לנו דרך לחשב את K, אז בהכרח תהיה תוכנית שבה הבעיה שתיארתי לעיל לא תתקיים. המסקנה המיידית היא שלא ניתן לחשב את K.

ובכן, הנה "תבנית" לתוכנית פרדוקסלית שכזו:

y=0

while true

 return y if K(y) > n

 y = y + 1

end

אני אומר "תבנית" כי הדבר הזה אינו תוכנית חוקית - הסימן n אינו מייצג משתנה. אם מחליפים אותו במספר, מקבלים תוכנית חוקית. למשל:

 

y=0

while true

 return y if K(y) > 100

 y = y + 1

end

כעת, מה האורך הכולל של התוכנית? כדי שהתוכנית תעבוד צריך שגם הקוד של K יהיה חלק ממנה - אבל אורך הקוד הזה קבוע, נסמנו U. פרט לכך אורך התוכנית שלי גם כן קבוע כמעט לגמרי - נסמן את הגודל הקבוע בתור C. מה כן משתנה? הגודל של המספר שאני כותב במקום n. הרי אם כתבתי 100, הוספתי עוד שלושה תווים לתוכנית; אבל אם הייתי רוצה לכתוב 1000000 הייתי מוסיף בכך עוד שבעה תווים לתוכנית. כאן אנחנו מגיעים לנקודה העדינה ביותר בכל הסיפור - המקום שהמספר שאני כותב במקום n תופס שווה ללוגריתם (בבסיס 10) של המספר עצמו. כלומר, בשביל לייצג את המספר מאה אני צריך רק שלושה תווים. בשביל לייצג את אלף - ארבעה, וכן הלאה. בכל פעם שבה גודל המספר מוכפל ב-10 אני צריך להוסיף רק תו אחד נוסף לייצוג. במילים אחרות - גודל התוכנית שלי גדל יחסית לאט בזמן שאני מגדיל את n מאוד מהר.

גודל התוכנית הכולל, אם כן, ניתן לכתיבה בתור \( U+C+\log n \). כעת אנחנו מוכנים לקטוף את הפרדוקס. אנחנו יודעים שהתוכנית תדפיס מספר שסיבוכיות קולמוגורוב שלו גדולה מ-\( n \); ולכן אם נבחר \( n_0 \) גדול מספיק כך שיתקיים \( U+C+\log n_0 < n_0 \) נגיע לסתירה - כי הנה, התוכנית שלנו הדפיסה מספר שמנכונות K מובטח לנו שסיבוכיות קולמוגורוב שלו היא גדולה מ-\( n_0 \), אבל הסיבוכיות שלה נמוכה יותר מ-\( n_0 \). מובטח לנו שקיים \( n_0 \) שכזה כי n גדל מהר יותר מאשר הלוגריתם שלו (ואילו U,C הקבועים הם חסרי השפעה בטווח הארוך).

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