בתשובה לשלוסמם, 14/07/09 19:03
 |
|
 |
||
|
||||
 |
אה, הבנתי. מה שאתה מציע כאן הוא להגדיר אקראיות בעזרת סיבוכיות קולמוגורוב (שזו גישה לגיטימית בהחלט, אבל לא הגישה שעליה דיברתי במאמר). לרוע המזל, אני עדיין לא חושב שמה שאתה מציע הוא אפשרי, גם לא תיאורטית. שורש הבעיה נעוץ בכך שבהינתן אלגוריתם, אין לך דרך לדעת האם הוא עוצר או לא. אמנם, אם כל מה שאנחנו מדברים עליו הוא n יחיד, ספציפי, אז אפשר, תיאורטית, לדבר על "רשימת כל האלגוריתמים העוצרים מאורך קטן מ-n"; אבל זה לא מקדם אותנו לקראת אלגוריתם שמסוגל להגיד על *כל* מחרוזת אם היא אקראית (למעשה, אם אתה מגביל את האורך האפשרי של המחרוזות שהאלגוריתם צריך לטפל בהן, אז מבחינה תיאורטית הבעיה טריוויאלית - אני לא בטוח אם כדאי להיכנס לזה כרגע). |
 |
 |
 |
|
|
|
||
|
||||
|
לא הבנתי. למה זה לא מקדם אותנו? הרי אנחנו מדברים על רצף סופי. אם עבור כל n ניתן לדבר על "רשימת כל האלגוריתמים העוצרים מאורך קטן מ-n" (עבור כל n נכין את הרשימה מחדש - אם יש לנו מתכון הכנה כזה) אז ניתן להוכיח עבור כל רצף מאורך n שהוא רצף אקראי. כלומר יש לנו אלגוריתם ל"כל" מחרוזת סופית. מש"ל. | |
|
|
|
|
|
||
|
||||
|
שורש הבעיה נעוץ באמירה "נכין את הרשימה מחדש". אנחנו *לא* יודעים להכין את הרשימה; אנחנו רק יודעים שיש כזו, אבל אין לנו מושג מהי. אנחנו לא מסוגלים לייצר אותה באופן אלגוריתמי. מה שאנחנו מדברים עליו עכשיו הוא אחת מהנקודות העדינות הבסיסיות בתורת החישוביות - ההבדל בין מודל חישוב יוניפורמי ללא יוניפורמי. אנסה לתת דוגמה שאולי תבהיר את זה: כל אלגוריתם אפשר לקודד באמצעות מספר טבעי. נבחר שיטת קידוד כלשהי. עכשיו, ברור שלכל מספר טבעי n קיים אלגוריתם שמכריע האם n הוא קידוד של תוכנית שעוצרת על הקלט הריק. האלגוריתם הזה הוא אחד משניים - או האלגוריתם שתמיד אומר "כן", או האלגוריתם שתמיד אומר "לא". לרוע המזל, אנחנו לא יודעים מי מהם הוא האלגוריתם הנכון, אבל ברור לנו שאחד מהם נכון - ולכן בפרט *קיים* אלגוריתם שפותר את הבעיה עבור ה-n הספציפי. עכשיו לך תשלב את כל אינסוף האלגוריתמים הללו לאלגוריתם כללי שבהינתן n אומר האם n הוא קידוד של תוכנית שעוצרת על הקלט הריק (רמז: אי אפשר). |
|
|
|
|
|
|
||
|
||||
|
''אנחנו לא מסוגלים לייצר אותה באופן אלגוריתמי'' אם אנחנו יודעים שקיימת הוכחה עבור כל אלגוריתם , אז ניתן לעבור על כל ההוכחות האפשריות. |
|
|
|
|
|
|
||
|
||||
|
אין "הוכחה". יש אלגוריתם שעונה נכון, אבל אין לך בהכרח הוכחה שהוא עונה נכון (בפרט, אם התשובה לשאלה "האם האלגוריתם עוצר?" היא "לא", אין לזה הוכחה). | |
|
|
|
|
|
||
|
||||
|
אם כך אתה צודק, משום מה היה זכור לי שיש *הוכחה*. אנסה לנבור הלילה בספרים. אגב, רמזת שאתה מכיר שיטה אחרת (לא פולינומיאלית) המוכיחה שמחרוזת סופית היא אקראית, אפשר בבקשה הפניה? |
|
|
|
|
|
|
||
|
||||
|
מה הפירוש של הוכחת אקראיות של מחרוזת סופית? הרי *כל* מחרוזת באורך נתון תתקבל בסופו של דבר, בהסתברות 1, מדגימות בלתי תלויות מתוך התפלגות אחידה. אפשר לחשב את האנתרופיה של המחורזת, אפשר לחשב היוריסטיקות שאמורות למדוד את הסיבוכיות האלגוריתמית שלה, ואפשר להפעיל מבחנים סטטיסטיים להערכת הסבירות שהמחרוזת תתקבל מדגימה אקראית - אבל אף אחד מהדברים האלה מן הסתם לא *מוכיח* שום דבר לגבי הדרך בה המחרוזת הופקה. אגב, בבעיה בן דן המאמר שמעלינו התנאים שונים, וידוע בדיוק איך המחרוזת הופקה: תהליך דטרמיניסטי לחלוטין שגם הוא ידוע לחלוטין (עד כדי הגרעין). |
|
|
|
|
|
|
||
|
||||
|
ההגדרה על פי סיבוכיות קולמוגורוב, ועיין לעיל | |
|
|
|
|
|
||
|
||||
|
אז מה השאלה? "איך מחשבים סיבוכיות אלגוריתמית"? | |
|
|
|
|
|
||
|
||||
|
אני מצטרף לתהיה. הפסיק להיות לי ברור מה השאלה לפני כמה תגובות (אבל מדי פעם כשמזכירים משהו מעניין אני מרגיש צורך להגיב, למשל לציין שאפשר להוכיח שאי אפשר להראות חסמים תחתונים לא טריוויאליים לסיבוכיות קולמוגורוב של מחרוזות, למעשה זו מדובר בהוכחה אלטרנטיבית למשפט אי השלמות של גדל). בתגובה זו קיים אי דיוק (אחד שאני מודע אליו ואולי עוד). מושאר כתרגיל לקורא המשועמם. |
|
|
|
|
|
|
||
|
||||
|
לא הסברתי את עצמי טוב. יש כמה גישות למושג האקראיות - אחת מסתמכת על סיבוכיות קולמוגורוב. אחרת מתבססת על אי קיום מבחין - ובמקרה הזה, אין משמעות לדבר על אקראיות של מחרוזת ספציפית, רק על האקראיות של המחולל. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |