מפגש עשירי- 17.05.23

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