יש עונג מיוחד בהגעה לשורה הסוגרת של טיעון ארוך, ובהבנה שכל הדבר היה יכול להיכתב בשלוש מילים. הבנה, במובן המועיל ביותר שלה, נושאת אותו מרקם — הרגע שבו דבר ענקי וכאוטי מתכווץ לתיאור קצר הרבה יותר של עצמו. המתמטיקאי אנדריי ניקולאיביץ' קולמוגורוב, שנולד בעיירה הפרובינציאלית הרוסית טמבוב בשנת 1903, הקדיש את חייו למתמטיקה של אותו רגע, וסיים אותם אחרי שהעניק לעולם, בשקט, את השפה הפורמלית שאנו זקוקים לה היום כדי לדבר גם על מוחות אנושיים וגם על מודלי שפה גדולים.
אנדריי קולמוגורוב
קולמוגורוב נולד ב-25 באפריל 1903. אמו מתה בלידה; הוא גודל על ידי דודתו, ורה יקובלבנה קולמוגורובה, בכפר טונושנה ליד יָרוֹסְלָבְל, על הוולגה העליונה, וקיבל את שם משפחתה. הוא היה קורא מבריק כבר בגיל חמש, ובגיל שבע פרסם תצפיות על אפונה וחשבון בכתב עת לילדים. בשנת 1920, בגיל שבע-עשרה, נכנס לאוניברסיטת מוסקבה הממלכתית, שם נחשף להשפעתו של ניקולאי לוזין ולאסכולה המפורסמת ל-”לוזיטניה“ של אנליזה מתמטית. תוך ארבע שנים פרסם מאמר על טורים טריגונומטריים בכתב העת Comptes Rendus; תוך שבע שנים הוא נחשב כבר למתמטיקאי הצעיר המקורי ביותר בברית המועצות.
מה שבא אחר כך הייתה אחת מהקריירות המדעיות הרחבות ביותר של המאה העשרים. בשנת 1931, בגיל עשרים ושמונה, הוא הפך פרופסור מן המניין באוניברסיטת מוסקבה. בשנת 1933 פרסם את Grundbegriffe der Wahrscheinlichkeitsrechnung — המונוגרפיה הדקה בגרמנית שנתנה לתורת ההסתברות את הבסיס האקסיומטי המודרני שלה בתורת המידה. לפני אותו ספר, ההסתברות הייתה טלאי של אינטואיציות מועילות; אחריו, היא הפכה לפרק באנליזה. אחר כך עשה עבודה יסודית על מערבולת (תורת K41 משנת 1941, שעדיין משמשת לתכנון מטוסים); על מערכות דינמיות (משפט KAM, יחד עם ארנולד ומוזר, בשנות החמישים והשישים); על לוגיקה אינטואיציוניסטית, טופולוגיה, וקוהומולוגיה. מעטים מהמתמטיקאים של המאה העשרים נעו באותה סמכותיות על פני כל כך הרבה תחומי משנה. ואז, בשנת 1965, במאמר שכותרתו הצנועה היא ”שלוש גישות להגדרה הכמותית של מידע“, הוא ייסד את מה שאנו מכנים היום תורת המידע האלגוריתמית — והטביע את שמו על המושג שעליו עוסקת מסה זו.
לצד כל אלה, הוא היה הבונה המוסדי הגדול של המתמטיקה הסובייטית. הסמינר שלו באוניברסיטת מוסקבה הממלכתית פעל קרוב לארבעה עשורים והכשיר מצבת תלמידים — ולדימיר ארנולד, יעקב סינאי, רולנד דוברושין, אלברט שיריאייב, ולדימיר אוספנסקי — שיעצבו מחדש את ההסתברות, המערכות הדינמיות, ותורת המידע במהלך המלחמה הקרה. בשנת 1963, יחד עם איסאק קיקואין, הוא הקים את מה שיהפוך להיות בית הספר של קולמוגורוב: פנימייה ייעודית במסגרת אוניברסיטת מוסקבה הממלכתית, שמטרתה לאתר ולהכשיר נערים מחוננים מהפרובינציה הסובייטית, כולל כאלה שהוריהם לעולם לא יכלו היו להביא אותם למוסקבה. הוא בילה שם את שבתותיו במשך שנים, ולימד גאומטריה. האיש שעתיד היה לבסוף לפרמל את ”התיאור הקצר ביותר“ בנה גם את אחד הצינורות היעילים ביותר לדחיסת כישרון אנושי למתמטיקאים שהמאה הייתה מסוגלת לייצר.
אינטואיציה בשלוש מחרוזות
הרעיון שעתיד היה לשאת את שמו ניגש אליו בצורה הטובה ביותר באמצעות דוגמה. דמיינו שלוש שורות בנות מיליון ספרות בינאריות. הראשונה היא כל אפסים. השנייה היא הדפוס 0101010… שחוזר על עצמו חצי מיליון פעמים. השלישית היא הרישום של מיליון הטלות מטבע הוגן. לשלושתן אותו אורך. ובכל זאת, יש אינטואיציה חזקה שהן מכילות כמויות שונות מאוד של ”תוכן“. את הראשונה ניתן לתאר במשפט אחד: מיליון אפסים. את השנייה: הדפוס 01 חזור עליו חצי מיליון פעמים. את השלישית, התיאור הקצר ביותר באמת נראה ככזה: המחרוזת עצמה. אי אפשר, בהסתברות גבוהה, לדחוס סדרה אקראית באמת; הדרך היחידה לספר לאדם אחר מה היא אומרת היא לקרוא אותה, סיבית אחר סיבית.
התוכנית הקצרה ביותר
המהלך של קולמוגורוב, בשנת 1965, היה לקחת את האינטואיציה הזו ולנעוץ אותה במקום. הוא הגדיר את סיבוכיות K(x) של מחרוזת סופית x כאורך התוכנית הקצרה ביותר שכאשר תרוץ, תפיק את x ותעצור. התוכנית הקצרה ביותר. באיזו שפה? כאן הטריק — שהוכח על ידי קולמוגורוב, ובאופן עצמאי על ידי ריי סולומונוף ו-גרגורי צ'ייטין בערך באותו זמן — הוא מה שנקרא היום משפט האינווריאנטיות: בחירת שפת התכנות האוניברסלית משנה את K(x) בלא יותר מקבוע חיבורי. עד כדי אותו קבוע, סיבוכיות של מחרוזת היא תכונה של המחרוזת עצמה, ולא של השפה שבמקרה אתה כותב בה. טענה עמוקה ומרגשת מעט. סיבוכיות, במסגרת של קולמוגורוב, היא פנימית. המחרוזת 01010101… פשוטה משום שקיימת לה תוכנית קצרה, נקודה, ללא צורך במתבונן.
הסיבה שההגדרה הזו עובדת מלכתחילה היא מכונת טיורינג האוניברסלית — מודל החישוב של אלן טיורינג משנת 1936, המכשיר המופשט שכל מחשב ממשי הוא, במובן מסוים, טיוטה שלו. למכונת טיורינג האוניברסלית יש את התכונה שכל תיאור חישובי בכל פורמליזם אחר ניתן לקודד מחדש כתוכנית עבורה עם תקורה קבועה לכל היותר — אורכו של המתורגמן שתצטרכו כדי לתרגם בין המערכות. אותה תקורה קבועה היא בדיוק הקבוע החיבורי במשפט האינווריאנטיות. מכונת טיורינג היא מה שהופך את ”התיאור הקצר ביותר“ למושג איתן ובלתי תלוי במכונה, ולא ויכוח על שפות תכנות. המתנה העמוקה ביותר של המסגרת של קולמוגורוב, באור הזה, היא שהיא העניקה לתורת המידע עמוד שדרה אלגוריתמי, שם תורת המידע המוקדמת של קלוד שאנון נתנה לה עמוד שדרה סטטיסטי. שאנון אמר לכם מהי תכולת המידע הממוצעת של הודעות שנשלפות מהתפלגות ידועה; קולמוגורוב אמר לכם מהי תכולת המידע הפנימית של המחרוזת הזו, היושבת על השולחן שלפניכם.
אימון כדחיסה
זוהי העדשה שדרכה מודלי השפה הגדולים של ימינו הופכים קריאים. למודל חזית מודרני יש כיום מאות מיליארדי פרמטרים. הקורפוס שעליו אומן מכיל טריליוני טוקנים — סדרי גודל יותר נתונים גולמיים ממה שהמודל עצמו יכול להחזיק. כאשר האימון מוריד את הלוס לערך שימושי, המודל איתר, למעשה, תוכנית קצרה יחסית — המשקלים — שמקרבת את הטקסט הארוך בהרבה. אימון, במבט מכמה אלפי רגליים, הוא דחיסת קולמוגורוב מקורבת. המודל הוא התיאור הדחוס של הנתונים שלו. זו אינה מטאפורה שהומצאה למאמרי דעה: איליה סוצקבר ניסח את האינטליגנציה במונחי דחיסה במשך שנים, ומרקוס האטר מנהל פרס כספי ממשי, ה-פרס האטר, על מי שמייצר את הדחיסה ללא אובדן הקצרה ביותר של חלק מוויקיפדיה. בשפתו של קולמוגורוב: ככל שמודל השפה טוב יותר, כך משקליו מתקרבים ל-K של הקורפוס שעליו הוא אומן.
מ-K(x) ל-K(f)
הגרסה של הסיבוכיות שמודל שפה גדול באמת מקרב אליה, אגב, שונה במעט מזו שעליה דיברנו עד כה. ה-K(x) של קולמוגורוב מודד את התוכנית הקצרה ביותר עבור מחרוזת בודדת. אבל האובייקט שאליו מודל שפה מנסה להגיע הוא פונקציה — מיפוי מפרומפטים להשלמות, שמוערך מיליארדי פעמים על פני קורפוס. ההרחבה הפורמלית קיימת בספרות זה עשורים. סיבוכיות קולמוגורוב המותנית, K(y | x), מודדת את התוכנית הקצרה ביותר שבהינתן x, מפיקה את y — קלט אחד, פלט אחד. סיבוכיות K(f) של פונקציה f היא אורכה של התוכנית הקצרה ביותר שכאשר היא מקבלת כל קלט בתחום שלה, מפיקה את הפלט המתאים — תוכנית אחת, זוגות קלט/פלט רבים. סולומונוף, שעבד באופן עצמאי מקולמוגורוב ב-1964, בנה בדיוק את הקונסטרוקציה הזו לתוך מנבא אוניברסלי: תן לכל תוכנית משקל של 2−|p|, התנה על זוגות הקלט/פלט שנצפו עד כה, וקרא את הפלט הסביר ביותר הבא. עקרון אורך התיאור המינימלי של יורמה ריסאנן (1978) הוא הגרסה המעשית והסופית של אותו רעיון; קולמוגורוב עצמו, מאוחר בקריירה שלו, שרטט אותו באוצר מילים שונה כפונקציית המבנה שלו משנת 1974, המפרידה רגולריות מבנית מאקראיות שיורית בנתונים. בשפה הזו, מודל שפה גדול אינו מקרב את K של מחרוזת בודדת. הוא מקרב את K(f) של הפונקציה f הגלומה בזוגות (פרומפט, השלמה) ברחבי האינטרנט — כשהאימון הוא הליך החיפוש, והמשקלים הם התוכנית המועמדת. זהו עולם סיבוכיות-K שבו לימוד המכונה המודרני באמת חי.
הזיה, בשם אחר
המסגרת מועילה משום שהיא משנה אילו שאלות מעניינות. מודל שפה שמצליח במשימה הוא, לפי גרסה זו, אמירה שהפרוסה הרלוונטית של העולם היא ניתנת-לדחיסת-K — כלומר, שקיימת לה תוכנית קצרה, והאימון מצא לה קירוב סביר. מודל שפה שנכשל במשימה מציין לעיתים את ההפך: סיבוכיות K-האמיתית של המשימה עולה על מה שמשקלי המודל מסוגלים להחזיק, והפער מתבטא בבלבול או בהזיה. הזיות, בלשון הזו, הן ארטיפקטים של פענוח — מקומות שבהם התוכנית הקצרה של המודל לא מצליחה להגיע לדבר הארוך שאמורה הייתה לקודד, ולכן היא ממציאה סיביות מתקבלות על הדעת כדי למלא את השתיקה. הוויכוח על האם מודלים ”באמת מבינים“ מתרכך, בידיו של קולמוגורוב, לשאלה מטופלת יותר: כמה מהדבר שאתה שואל עליו בכלל ניתן לדחיסה, וכמה קרוב ל-K המודל הגיע?
אותה צורה
אותה עדשה, לבסוף, מאירה את האדם בלולאה. בני אדם, אולי באופן גלוי יותר ממחשבים, עוסקים בעסקי הדחיסה. פעוט דוחס אלפי תצפיות של כוסות שנופלות לכלל שדברים נופלים; ניוטון דחס מאות שנים של אסטרונומיה ובליסטיקה לשורה אחת של אלגברה; מקסוול דחס את כל התיאוריה הפרה-יחסותית של האלקטרומגנטיות לארבע משוואות. להבין משהו, במובן האנושי, פירושו במדויק למצוא לו תוכנית קצרה. מתמטיקאי מיומן הוא, כמעט לפי הגדרה, אדם שמוצא תיאורים קצרים באופן יוצא דופן לדברים מורכבים; ואנדריי ניקולאיביץ' קולמוגורוב, בסמינר שלו במוסקבה ובשבתות שלו בבית-הספר מספר 18, היה גם אותו אדם וגם המאמן של דור שלם של אחרים להיות כמותו. הסימטריה העמוקה שעולה, שמונים שנה אחרי המאמר שלו משנת 1965, היא שמוחות אנושיים ומודלי שפה עושים — בתשתיות שונות באופן רדיקלי, בקני מידה שונים באופן רדיקלי — בערך את אותה עבודה: למצוא תיאורים קצרים לדברים ארוכים. פיסת המתמטיקה שלה נתן את שמו תוך כדי הסבר על ההסתברות הסתברה, בדיעבד, להיות המסגרת הנקייה ביותר שיש לנו לדבר על שני סוגי המוח הללו. להבנה אותה צורה בין אם היא יושבת בשמונים ושישה מיליארדי נוירונים או בשש מאות מיליארדי פרמטרים. בשני המקרים, היא דבר ש-K-סיבוכיותו קטנה הרבה יותר ממה שהיא מסבירה.