מפגש שני- 12.1.23:

 

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

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