מפגש - 9.2.23

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