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