פרדוקסים לגבי דחיסת נתונים

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

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

המשמעות היא שמספר זה יתאים לייעוד "המספר הקטן ביותר שעבורו שמונים אותיות לא מספיקות", שיש לו רק 78 אותיות! מצד אחד, מספר זה חייב להתקיים; מצד שני, אם המספר הזה קיים, אזי ייעודו אינו מתאים לו. פָּרָדוֹקס!

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

האם יש דרכים פורמליות לתאר את רצף (אלגוריתם) של פעולות על מספרים? יש, ובשפע - הן נקראות שפות תכנות. במקום סימונים מילוליים, נשתמש בתוכנות (למשל ב-Python) שמציגות את המספרים הנדרשים. למשל, לחמש תשע התוכנית מתאימה print("9"*5). נמשיך להתעניין בתוכנית הקצרה ביותר עבור מספר נתון. האורך של תוכנית כזו נקרא מורכבות קולמוגורוב מספרים; זהו הגבול התיאורטי שאליו ניתן לדחוס מספר נתון.

במקום הפרדוקס של ברי, אנו יכולים כעת לשקול פרדוקס דומה: מהו המספר הקטן ביותר שתוכנית קילובייט אינה מספיקה לפלט?

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

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

מה הקאץ' עכשיו? כבר לא ניתן לייחס את זה לאי-רשמיות של הסימון!

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

או שזה לא יגמר? ואכן, בין כל התוכניות שנוסו, יהיו while True: pass (והאנלוגים הפונקציונליים שלה) - והעניין לא ירחיק לכת מבדיקת תוכנית כזו!

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

מקור: www.habr.com