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