בתשובה לענן כחול, 08/02/13 7:07
 |
|
 |
||
|
||||
 |
הנה איך שאני מבין את זה. כשהילברט ניסח את הבעיות שלו היה למתמטיקאים מושג אינטואיטיבי של מה זה אלגוריתם, ותחושה של "אני יודע לזהות אלגוריתם כשאני רואה אותו", אבל לא הגדרה קפדנית. וללא הגדרה כזו ברור שאי אפשר להוכיח הוכחה קפדנית. מה שצ'רץ' וטיורינג עשו הוא הגדרה קפדנית (אלגוריתם = מכונת טיורינג), אבל הוא לא יותר מהגדרה. אין בו הבטחה שאלגוריתם במובנו הזה מתלכד בדיוק עם המושג האינטואיטיבי, ואפשר לומר שהוא צמצום של המושג האינטואיטיבי. בכל זאת יפה שנעשה המאמץ להראות שעד כמה שאנחנו יודעים "לזהות אלגוריתם כשאנחנו רואים אותו" אז הוא כן מתלכד עם ההגדרה של טיורינג וצ'רץ'. אז במובן המצומצם של אלגוריתם - המובן הצ'רצ'י-טיורינגי, יש פתרון לבעיות של הילברט. במובן הכללי, של המושג האינטואיטיבי, הבעיות לא נפתרו, אבל נראה לי די ברור שהן לא יכולות להיפתר. במשך רוב ההיסטוריה של המתמטיקה המתמטיקאים לא הרגישו בעיה מיוחדת לעבוד עם מושגים אינטואיטיביים, אבל הסיפור הידוע עם אקסיומת המקבילים חולל את משבר יסודות המתמטיקה, ובעקבותיו הבינו שיש פער שאינו ניתן לגישור בין מושגים אינטואיטיביים לבין הוכחה קפדנית. הילברט כבר פעל בתוך העולם הזה. לכן כשהוא הציג את הבעיות שלו הוא היה חייב להניח שצעד ראשון לפתרונן - לפחות בצד של הוכחת אי-קיום האלגוריתמים1 - צריך להיות הגדרה קפדנית של "אלגוריתם", שנחמד אם היא תהיה קרובה איכשהו למושג האינטואיטיבי אבל סביר שהיא תהיה צמצום שלו. 1 או הוכחת קיום לא קונסטרוקטיבית, אם הוא העלה בדעתו דבר כזה. |
 |
 |
 |
|
|
|
||
|
||||
|
ויש עוד הערה מתחייבת: המילה "אלגוריתם" כשלעצמה לא מגדירה מהם הצעדים הבסיסיים שבהם הוא יכול להשתמש. אם הייתה אפשרות למיישם האלגוריתם היכולת ההיפותטית להשתמש בצעד הבסיסי "פתור משוואה דיופונטית", היה אלגוריתם פשוט מאוד לפתור משוואה דיופונטית. אבל במובן הרחב הזה הבעיה פשוטה וחסרת משמעות. |
|
|
|
|
|
|
||
|
||||
|
תקן אותי אם אני טועה, אבל בעולם המחשוב היום (וגם במכונת טיורינג מן הסתם) די ברור מהם הצעדים הבסיסיים, והם מאד מאד בסיסיים באמת1. וכמובן שכל הגדרת צעד סבוך יותר ניתנת לפרישה רקורסיבית, כשבתור 'אלגוריתם' תוכל להגדיר רק אלגוריתם שנפרש (ופורש למעשה) עד תומו2. 1 משהו כמו כל מה שאפשר לעשות עם שני ביטים, פלוס כתיבה לכתובת וקפיצה לכתובת, אתה בטח יודע את זה יותר טוב ממני. 2 זה מזכיר לי אסוציאטיבית את התיאור של פיינמן לאלקטרודינמיקה קוונטית, מתוך ספרו המאד מומלץ שסיימתי לקרוא (שוב) לאחרונה: QED - The strange theory of light and matter. בספר הזה, שהוא ספר מדע פופולרי ולכן לא משתמש בשום משוואות ('אלגוריתמים') מסובכות, הוא טוען ומסביר שכל מה שעושים בתורה הנ"ל, מתמצה בסיכום ארוך ומפרך של אמפליטודות ופאזות (או חצים קטנים בזוויות שונות אם נדייק בתיאורו). ואז הוא אומר שמה שלוקח לסטודנטים שלו 3 שנים של קורסי דוקטורט, זה ללמוד את האלגוריתמים היותר מסובכים שעושים את זה ביעילות - אינטגרלי מסלול וחיות אחרות (אנלוגי ל"פתור משוואה דיופנטית" שלך). הספר, אגב, בהחלט נמצא בשלישייה הראשונה של ספרי המדע הפופולרי שקראתי, ומומלץ בחום רב לכל מי שמתעניין בתורת הקוונטים (+) ומה שיש לה להגיד על פוטונים, אלקטרונים ומה שביניהם, שכמו שפיינמן אומר, מכסה לא רע את רוב התופעות שאנו חווים ביום-יום, מלבד כבידה כמובן. |
|
|
|
|
|
|
||
|
||||
|
בהתחלה רציתי לכתוב על ההערה שלי שהיא הערה נוקדנית (ניטפוק בעברית). אני חושב שמה שכתבת מובן בהחלט לכל מי שקצת מכיר את התחום ונכון אם אנחנו רוצים לייחס משמעות מועילה למונח הזה. אולם בעיקרון אין שום הבטחה תיאורטית שעוד חמש שנים לא יומצא איזה רכיב חישוב מופלא שמסתמך על המימדים המקופלים של תורת המיתרים1 ומצליח לשחרר אותנו ממגבלותיה של מכונת טיורינג. לא נראה לי שזה סביר במיוחד. בינתיים מכונת טיורינג הוכחה כשווה בכוחה לפחות לכל מודלי החישוב שהצלחנו לבנות בפועל. אבל נראה לי שהשואל המקורי התכוון בדיוק לבעיה הזו. וחוץ מזה, בתאוריה אתה יכול לנסות לתאר מודלי חישוב חלופיים. אם זה מועיל או לא, זו כבר שאלה אחרת. האנלוגיה שעולה במוחי היא האנלוגיה המתבקשת של מתכון. אם תידרש לכתוב מתכון תקין עבורי, תצטרך לכתוב אותו ברמת פירוט גבוהה יותר. יש גם כל מיני פעולות בסיסיות שבהן לא תוכל להשתמש. 1 הכנס כאן תיאור חלופי לבחירתך. |
|
|
|
|
|
|
||
|
||||
|
1 אפילו ברמה הלוגית לא בדיוק ברור לי מה אתה מצפה ומאיזה מגבלות ישחרר אותך הרכיב הנ"ל. אבל אולי זה בגלל המוח המוגבל שלי. | |
|
|
|
|
|
||
|
||||
|
בקיצור: אין שום הוכחה שכל מודל חישוב אפשרי שקול למכונת טיורינג. הדבר היחידי שאנחנו יודעים הוא שכל מודל חישוב שאנחנו יכולים לממש או אפילו יכולים לתאר שקול לה. מכאן "מסיקים" באינדוקציה (של פיזיקאים) שכל מודל חישוב שקול לה. | |
|
|
|
|
|
||
|
||||
|
סליחה על הניטפוק, אבל זה קצת נשמע כמו טאוטולוגיה, ''כל מודל חישוב שאנחנו יכולים לממש או אפילו יכולים לתאר שקול לה'', כאילו בזאת הגדרת מהו מודל חישוב. | |
|
|
|
|
|
||
|
||||
|
לא טאוטולוגיה (אבל לא משהו חכם במיוחד) - לכל מודל חישוב מעשי שהוצע, הודגם שהוא יכול להיות ממומש על ידי מכונת טיורינג. | |
|
|
|
|
|
||
|
||||
|
לא נכון. מכונת טיורינג לא יכולה להנפיק סדרה אקראית ויש מכשירים ש(על פי התיאוריה הפיזיקלית) יכולים. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |