מפגש שלישי - 26.1.23

 

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

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