בתשובה לשלוסמם, 12/07/09 14:30
שיטה פרקטית להבחנה באקראיות 516022
ליתר דיוק: אם הקובץ יתכווץ, הוא לא אקראי‏0. המסקנה ההפוכה לא בהכרח נכונה בגלל שגם תוכנת כיווץ יעילה לא יודעת למצוא את כל סוגי ה"מידע" או "סדר".

התפלגות האיברים היא רק מבחן פשוט אחד לאקראיות. היא לא תבחין במקרה הפשוט של הרצף 0, 1, 2, 3, 4, ... (וכשמגיעים למספר המקסימלי חוזרים ל־0. לדוגמה: אם מסתכלים על בתים אז אחרי 255 חוזרים לאפס). למעשה יש שיטות קידוד שבהן ההתפלגות האחידה היא דרישה בסיסית ללא קשר לשיקולי "אבטחה".

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

ואגב, למיטב ידיעתי ההכללה שלך על "מובנים בשפה" לא ממש נכונה.
שיטה פרקטית להבחנה באקראיות 516085
כשכתבתי התפלגות לא התכוונתי לכמות המספרים מכל סוג, (אגב בקובץ בינארי מופיעים כמובן רק 0,1) אלא התכוונתי על כל מבחן שתעלי בדעתך. (למשל אם קיימת הסתברות גבוהה במיוחד שנמצא את התנך נוסח קורן רשום איפה שהוא בקובץ האקראי , אז אני מצפה שנמצא אותו שם - אגב חשבתם על זה שהתנך רשום ככתבו איפה שהוא בפאי?)
חוצמיזה הרצף הפשוט של 0,1,2,3,4 יתכווץ כדבעי
שיטה פרקטית להבחנה באקראיות 516089
לגבי הטענה על התנ''ך בפאי, אף אחד לא יודע אם זה נכון או לא. אנשים משערים שפאי הוא מספר נורמלי ובמקרה הזה הטענה שלך נכונה, אבל (למיטב ידיעתי, נכון להיום) לא ידועה הוכחה להשערה זו.
שיטה פרקטית להבחנה באקראיות 516091
הסיכוי קצת יותר גבוה, מכיוון שיש הרבה שיטות לקודד את התנך.

לדוגמה, אם הקידוד יהיה מספר ה־ISBN, הסיכוי הופך פתאום להיות טוב למדי.
שיטה פרקטית להבחנה באקראיות 516101
ואם הקידוד הוא 1 אז בכלל!
שיטה פרקטית להבחנה באקראיות 516093
כמובן שהבעיה היחידה היא שאין מספיק זמן להריץ "כל מבחן שתעלי בדעתך" :-(
שיטה פרקטית להבחנה באקראיות 516323
אם הקלט הוא סופי (ואורכו n) אז יש מספיק זמן.
אם נגדיר פלט אקראי כפלט שלא ניתן ניתן לכיווץ - כלומר לא קיים אלגוריתם ליצירת הפלט שאורכו קצר יותר מהפלט. כל שעלינו לעשות הוא לעבור על כל האלגוריתמים (העוצרים) מאורך n-1. (אם אני לא טועה - עבור כל אלגוריתם לא עוצר מאורך סופי קיימת הוכחה שהוא לא עוצר)
שיטה פרקטית להבחנה באקראיות 516324
וכמה אלגוריתמים כאלו יש? (סדר גודל)
שיטה פרקטית להבחנה באקראיות 516340
2 בחזקת n-1
שיטה פרקטית להבחנה באקראיות 516326
בכל מקרה קיומו של אלגוריתם כזה תלוי במודל החישובי, ואין רצף שיענה לתנאי שלך בכל המודלים ביחד.
שיטה פרקטית להבחנה באקראיות 516329
ליתר דיוק: השאלה שבאמת מעניינת אותנו היא לא "האם אפשר להבחין‏17 בין הפלט הזה לבין רעש אקראי?" אלא "האם אפשר להבחין‏17 בין הפלט הזה לבין רעש אקראי בזמן סביר?".

המושג התאורטי (שוב: תאורטי. לא מעשי. אבל במקרה הזה כבר יש לו קשר למציאות) המקובל לגבי "זמן סביר" הוא זמן ריצה פולינומי. כלומר זמן הריצה גדר רק כפונקציה פולינומית של N ולא משהו יותר גרוע מהסוג של פונקציה מעריכית. ר' לדוגמה חישוב יעיל [ויקיפדיה].

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

17 בהסתברות גבוהה מספיק. לדוגמה: יש לנו מבחן שתופס רצף לא אקראי בהסתברות מסדר גודל של חצי ואחנו יכולים לחזור עליו בצורה בלתי־תלויה (כלומר: כשנחזור עליו שוב ההסתברות לתפוס רצף לא אקראי היא שוב מהסתברות חצי. ע"י מספיק חזרות אנחנו יכולים לקבל הסתברות טובה כרצונינו.

23 בעברית: שיעורי בית
שיטה פרקטית להבחנה באקראיות 516334
לכל קלט קיים אלגוריתם שמכווץ אותו לתו "1" בצורה שניתנת לשחזור אחר כך; כמובן שאותו אלגוריתם כנראה יפעל בצורה לא משהו על קלטים אחרים.

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

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

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

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

עכשיו לך תשלב את כל אינסוף האלגוריתמים הללו לאלגוריתם כללי שבהינתן n אומר האם n הוא קידוד של תוכנית שעוצרת על הקלט הריק (רמז: אי אפשר).
שיטה פרקטית להבחנה באקראיות 516370
''אנחנו לא מסוגלים לייצר אותה באופן אלגוריתמי''
אם אנחנו יודעים שקיימת הוכחה עבור כל אלגוריתם , אז ניתן לעבור על כל ההוכחות האפשריות.
שיטה פרקטית להבחנה באקראיות 516371
אין "הוכחה". יש אלגוריתם שעונה נכון, אבל אין לך בהכרח הוכחה שהוא עונה נכון (בפרט, אם התשובה לשאלה "האם האלגוריתם עוצר?" היא "לא", אין לזה הוכחה).
שיטה פרקטית להבחנה באקראיות 516372
אם כך אתה צודק, משום מה היה זכור לי שיש *הוכחה*. אנסה לנבור הלילה בספרים.
אגב, רמזת שאתה מכיר שיטה אחרת (לא פולינומיאלית) המוכיחה שמחרוזת סופית היא אקראית, אפשר בבקשה הפניה?
שיטה פרקטית להבחנה באקראיות 516375
מה הפירוש של הוכחת אקראיות של מחרוזת סופית? הרי *כל* מחרוזת באורך נתון תתקבל בסופו של דבר, בהסתברות 1, מדגימות בלתי תלויות מתוך התפלגות אחידה.

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

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

בתגובה זו קיים אי דיוק (אחד שאני מודע אליו ואולי עוד). מושאר כתרגיל לקורא המשועמם.
שיטה פרקטית להבחנה באקראיות 516394
לא הסברתי את עצמי טוב. יש כמה גישות למושג האקראיות - אחת מסתמכת על סיבוכיות קולמוגורוב. אחרת מתבססת על אי קיום מבחין - ובמקרה הזה, אין משמעות לדבר על אקראיות של מחרוזת ספציפית, רק על האקראיות של המחולל.
שיטה פרקטית להבחנה באקראיות 516361
דווקא קיימת הוכחה שאין תוכנית שמסוגלת להכריע בזמן סופי האם אלגוריתם שרץ על הקלט הריק עוצר. הבעיה הזו היא שינוי קל (ולא מהותי) של בעיית העצירה [ויקיפדיה].
שיטה פרקטית להבחנה באקראיות 516365
אולי הוא מתבלבל עם אלגוריתמים בעלי זיכרון חסום, עבורם דווקא אפשר (ואפילו קל, בזמן אקספוננציאלי) לדעת אם הם עוצרים או לא (סאוויץ').
שיטה פרקטית להבחנה באקראיות 516369
לא קשור לסאוויץ' (שמדבר על הקשר בין דרישות הזכרון של אלגוריתם אי דטרמיניסטי ואלגוריתם דטרמיניסטי שקול), אלא סתם לכך שמספר הקונפיגורציות של אלגוריתם כזה הוא סופי.
שיטה פרקטית להבחנה באקראיות 516380
אצלי זה מתקשר משום מה אבל אתה צודק, זה לגמרי אוברקיל למקרה של מכונה דטרמיניסטית. אז חידה (אני מקוה שלא קלה מדי): מה סיבוכיות המקום הנדרשת על מנת להכריע אם מכונת טיורינג (דטרמיניסטית ללא קלט) בסיבוכיות מקום s עוצרת או לא?
שיטה פרקטית להבחנה באקראיות 516397
החסם העליון הסטנדרטי הוא אקספוננציאלי ב-s (במדויק, גודל האלפבית בחזקת s, ועוד לוג של s, ועוד לוג של גודל קבוצת המצבים). אני מפספס כאן משהו?
שיטה פרקטית להבחנה באקראיות 516421
סיבוכיות המקום.
שיטה פרקטית להבחנה באקראיות 516424
אוי, בעצם יש פתרון טריוויאלי למה ששאלתי. אז בואו נגיד שהאלגוריתם צריך לעבוד אפילו בלי לדעת את s.
שיטה פרקטית להבחנה באקראיות 516432
הפתרון הקודם שלי עשה מיש-מש - התחלתי מסיבוכיות הזמן, ואז עברתי לסיבוכיות המקום (אקספוננציאלי ב-s, אבל אז לוגריתמי ב-s?). מן הסתם סיבוכיות המקום, במקרה הקודם, היא s ועוד הלוגים הללו.

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

מה שכן, האלגוריתם שהצעת עלול לקחת זמן רב הרבה יותר מהדרוש. אתה יודע לתת אלגוריתם עם סיבוכיות מקום טובה ועם סיבוכיות זמן כמו של האלגוריתם הנאיבי (כלומר פרופורציונית למספר המצבים בפועל של המכונה ולא לחסם העליון)? החידה הזו נעשית יותר מדי "תפורה", אני אבין אם תעדיף לפרוש.
שיטה פרקטית להבחנה באקראיות 516620
אפשר אולי להשתמש בתעלול הסטנדרטי למציאת אורך מעגל - מבצעים שתי ריצות במקביל שאחת מהן מהירה פי שתיים יותר מהשנייה, ובכל סיבוב בודקים אם יש ''התנגשות'' (ליתר דיוק, אם ההרצה המהירה עקפה את ההרצה האיטית).
שיטה פרקטית להבחנה באקראיות 516634
כן, זה מה שרציתי. כאמור, פעם הבאה יהיה (אולי) יותר טוב.
שיטה פרקטית להבחנה באקראיות 516637
זו חידה יפה דווקא, אם כי לא נראה לי שמי שלא מכיר את תעלול המעגל יחשוב על הפתרון שכיוונת אליו (נראה לי שהם כן יוכלו למצוא את הפתרון הנאיבי יותר של ספירת הקונפיגורציות).
שיטה פרקטית להבחנה באקראיות 516646
הנחמד בעיני (אתה הזכרת לי את זה בהערה שלך על סאוויץ') הוא המעבר בין השאלה החישובית לשאלה קומבינטורית/אלגוריתמית על גרף הקונפיגורציות.
שיטה פרקטית להבחנה באקראיות 517000
למרות שעכשיו ברור הפתרון, איך מנוסחת החידה על אורך מעגל?
שיטה פרקטית להבחנה באקראיות 517009
יש לך מעגל שנתון באמצעות רשימה מקושרת (כלומר, סדרה של מצביעים שכל אחד מצביע לכתובת של הבא). תמצא את האורך שלו.

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

שמא לתת כנתון לא רק מעגל, אלא גרף קשיר שמכיל מעגל?
שיטה פרקטית להבחנה באקראיות 517026
אה... כן, זה כמובן מה שהתכוונתי אליו (גרף קשיר שמכיל מעגל).
שיטה פרקטית להבחנה באקראיות 517077
ואז, כשזיהית ששני ה"פועלים" שלך באותו מקום, כבר השלמת סיבוב, אבל צריך לעשות אותו שוב כדי לספור, נכון?
שיטה פרקטית להבחנה באקראיות 517079
אז מה. זה לא מוסיף לסיבוכיות (לכל היותר מעלה את זמן הביצוע פי 1.5 או משהו בסביבה).
שיטה פרקטית להבחנה באקראיות 517167
ברור. זה רק גורע, ואני קטנוני פה, שמץ של שמץ מהחן של הפתרון, בעיקר אם לפני-כן חשבת שנתון שאתה על המעגל, שאז זה לא נחוץ.
שיטה פרקטית להבחנה באקראיות 517199
העניין הוא שלא חושבים כך. למשל, בדוגמה שהתחילה את העניין (סימולציה של מכונת טיורינג עם חסם זכרון) לא ידוע אם בכלל יש מעגל, ומאוד לא סביר שנהיה עליו כבר בהתחלה.
שיטה פרקטית להבחנה באקראיות 517200
הנוסח שאני מכיר הוא למצוא אם רשימה מקושרת מכילה מעגל.
שיטה פרקטית להבחנה באקראיות 516367
אין תוכנית שמסוגלת להכריע עבור כל האלגוריתמים האפשריים, אבל לכל אלגוריתם ספציפי יש הוכחה משלו
שיטה פרקטית להבחנה באקראיות 516342
מאוד קל למצוא מבחן שמבדיל בין רצף המגיע ממחולל פסאודו-אקראי לרצף אקראי באמת. פשוט עוברים על כל הגלעינים האפשריים למחולל ובודקים אם אחד מהם מייצר את הרצף שבידינו. במילים אחרות: רצף ממחולל פסאודו-אקראי הוא תמיד דחיס לאורך הגלעין. ההוכחה שהאלגוריתם באמת מבחין - תרגיל לקורא.

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

חזרה לעמוד הראשי המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים