 |
|
 |
||
|
||||
 |
האם ניתן להוכיח שאלגוריתם שקול למכונת טיורינג? כפי שחלקנו יודעים ב-1900 התכנסו מיטב המתמטיקאים ושם העלה הילברט 23 בעיות פתוחות. אחת מהן , המכונה הבעיה העשירית , למצוא אלגוריתם שייקבע בהינתן משוואה דיופנטית , האם היא פתירה. בנוסף , ואני מצטט מתוך הבלוג "לא מדויק" של ד"ר גדי אלכסנדרוביץ': "אתגר אחר של הילברט, אותו הציג בשנת 1928 וזכה לשם הקליל Entscheidungsproblem, היה הבעיה הבאה: למצוא אלגוריתם אשר בהינתן טענה כלשהי שמנוסחת בשפה הפורמלית של הלוגיקה". ...... " מרגע שהסכמנו עם הפורמליזם של טיורינג, קל מאוד לראות שה-Entscheidungsproblem בלתי פתירה, לפחות עבור המודל שלו (אבל אם אנחנו מסכימים שהמודל של טיורינג תופס את כל מה שראוי להיקרא "אלגוריתם", זה סוגר את הבעיה לגמרי)". אני לא בקיא בהוכחת המשפט העשירי - כיצד מוכיחים שאין אלגוריתם שבהינתן משוואה דיופנטית האם היא פתירה. אבל לגבי ה-Entscheidungsproblem , אני מבין שההוכחה שאין אלגוריתם כנ"ל מתבססת על השערת צ'רץ' שכל מכונה חישוב סבירה שקולה למכונת טיורינג. כלומר אם אני מבין נכון , למעשה בהוכחה מסתמכים על כך שהמודל של טיורינג תופס את כל מה שראוי להיקרא "אלגוריתם". אבל במתמטיקה לא מסתמכים על "תיזות" , אלא על הוכחות חד משמעיות ולא על תחושות בטן! (אני בטוח שמדובר בהרבה יותר מ"תחושת בטן" ועדיין כפי שאני רואה זאת , במתמטיקה זה שחור ולבן - יש הוכחה או אין הוכחה , אין אמצע!) אם כך , האם למעשה אין הוכחה שאין אלגוריתם? האם ההוכחה מוכיחה שאין מכונת טיורינג ומכך לפי תזת צ'רץ' מניחה שאין אלגוריתם? (כי אני למשל לא רוצה לקבל את התזה שלו ללא הוכחה). אם כך , למעשה ה-Entscheidungsproblem לא הוכחה עד עצם הזה , ואולי גם הבעיה העשירית! את השאלה הזו כבר שאלתי לפני זמן מה בפורום תפוז "עבודה בהייטק" , ואני מצרף את הלינק גם כדי שתוכלו להתרשם מהתשובות שקיבלתי וגם כדי שתראו בדיוק למה התכוונתי בשאלתי. אני מפנה גם אליכם את השאלה הנ"ל , מכיוון שאני נהנה מהתגובות של הרבה אנשים כאן באתר , תגובות עמוקות ,פילוסופיות ועשירות ואני אשמח לכמה שיותר תגובות. למרות ששאלתי ספציפית , אתם יותר ממוזמנים גם לדון בדברים שמסביב לנושא וקשורים אליו. תודה רבה! |
 |
 |
 |
|
|
|
||
|
||||
|
הנה איך שאני מבין את זה. כשהילברט ניסח את הבעיות שלו היה למתמטיקאים מושג אינטואיטיבי של מה זה אלגוריתם, ותחושה של "אני יודע לזהות אלגוריתם כשאני רואה אותו", אבל לא הגדרה קפדנית. וללא הגדרה כזו ברור שאי אפשר להוכיח הוכחה קפדנית. מה שצ'רץ' וטיורינג עשו הוא הגדרה קפדנית (אלגוריתם = מכונת טיורינג), אבל הוא לא יותר מהגדרה. אין בו הבטחה שאלגוריתם במובנו הזה מתלכד בדיוק עם המושג האינטואיטיבי, ואפשר לומר שהוא צמצום של המושג האינטואיטיבי. בכל זאת יפה שנעשה המאמץ להראות שעד כמה שאנחנו יודעים "לזהות אלגוריתם כשאנחנו רואים אותו" אז הוא כן מתלכד עם ההגדרה של טיורינג וצ'רץ'. אז במובן המצומצם של אלגוריתם - המובן הצ'רצ'י-טיורינגי, יש פתרון לבעיות של הילברט. במובן הכללי, של המושג האינטואיטיבי, הבעיות לא נפתרו, אבל נראה לי די ברור שהן לא יכולות להיפתר. במשך רוב ההיסטוריה של המתמטיקה המתמטיקאים לא הרגישו בעיה מיוחדת לעבוד עם מושגים אינטואיטיביים, אבל הסיפור הידוע עם אקסיומת המקבילים חולל את משבר יסודות המתמטיקה, ובעקבותיו הבינו שיש פער שאינו ניתן לגישור בין מושגים אינטואיטיביים לבין הוכחה קפדנית. הילברט כבר פעל בתוך העולם הזה. לכן כשהוא הציג את הבעיות שלו הוא היה חייב להניח שצעד ראשון לפתרונן - לפחות בצד של הוכחת אי-קיום האלגוריתמים1 - צריך להיות הגדרה קפדנית של "אלגוריתם", שנחמד אם היא תהיה קרובה איכשהו למושג האינטואיטיבי אבל סביר שהיא תהיה צמצום שלו. 1 או הוכחת קיום לא קונסטרוקטיבית, אם הוא העלה בדעתו דבר כזה. |
|
|
|
|
|
|
||
|
||||
|
ויש עוד הערה מתחייבת: המילה "אלגוריתם" כשלעצמה לא מגדירה מהם הצעדים הבסיסיים שבהם הוא יכול להשתמש. אם הייתה אפשרות למיישם האלגוריתם היכולת ההיפותטית להשתמש בצעד הבסיסי "פתור משוואה דיופונטית", היה אלגוריתם פשוט מאוד לפתור משוואה דיופונטית. אבל במובן הרחב הזה הבעיה פשוטה וחסרת משמעות. |
|
|
|
|
|
|
||
|
||||
|
תקן אותי אם אני טועה, אבל בעולם המחשוב היום (וגם במכונת טיורינג מן הסתם) די ברור מהם הצעדים הבסיסיים, והם מאד מאד בסיסיים באמת1. וכמובן שכל הגדרת צעד סבוך יותר ניתנת לפרישה רקורסיבית, כשבתור 'אלגוריתם' תוכל להגדיר רק אלגוריתם שנפרש (ופורש למעשה) עד תומו2. 1 משהו כמו כל מה שאפשר לעשות עם שני ביטים, פלוס כתיבה לכתובת וקפיצה לכתובת, אתה בטח יודע את זה יותר טוב ממני. 2 זה מזכיר לי אסוציאטיבית את התיאור של פיינמן לאלקטרודינמיקה קוונטית, מתוך ספרו המאד מומלץ שסיימתי לקרוא (שוב) לאחרונה: QED - The strange theory of light and matter. בספר הזה, שהוא ספר מדע פופולרי ולכן לא משתמש בשום משוואות ('אלגוריתמים') מסובכות, הוא טוען ומסביר שכל מה שעושים בתורה הנ"ל, מתמצה בסיכום ארוך ומפרך של אמפליטודות ופאזות (או חצים קטנים בזוויות שונות אם נדייק בתיאורו). ואז הוא אומר שמה שלוקח לסטודנטים שלו 3 שנים של קורסי דוקטורט, זה ללמוד את האלגוריתמים היותר מסובכים שעושים את זה ביעילות - אינטגרלי מסלול וחיות אחרות (אנלוגי ל"פתור משוואה דיופנטית" שלך). הספר, אגב, בהחלט נמצא בשלישייה הראשונה של ספרי המדע הפופולרי שקראתי, ומומלץ בחום רב לכל מי שמתעניין בתורת הקוונטים (+) ומה שיש לה להגיד על פוטונים, אלקטרונים ומה שביניהם, שכמו שפיינמן אומר, מכסה לא רע את רוב התופעות שאנו חווים ביום-יום, מלבד כבידה כמובן. |
|
|
|
|
|
|
||
|
||||
|
בהתחלה רציתי לכתוב על ההערה שלי שהיא הערה נוקדנית (ניטפוק בעברית). אני חושב שמה שכתבת מובן בהחלט לכל מי שקצת מכיר את התחום ונכון אם אנחנו רוצים לייחס משמעות מועילה למונח הזה. אולם בעיקרון אין שום הבטחה תיאורטית שעוד חמש שנים לא יומצא איזה רכיב חישוב מופלא שמסתמך על המימדים המקופלים של תורת המיתרים1 ומצליח לשחרר אותנו ממגבלותיה של מכונת טיורינג. לא נראה לי שזה סביר במיוחד. בינתיים מכונת טיורינג הוכחה כשווה בכוחה לפחות לכל מודלי החישוב שהצלחנו לבנות בפועל. אבל נראה לי שהשואל המקורי התכוון בדיוק לבעיה הזו. וחוץ מזה, בתאוריה אתה יכול לנסות לתאר מודלי חישוב חלופיים. אם זה מועיל או לא, זו כבר שאלה אחרת. האנלוגיה שעולה במוחי היא האנלוגיה המתבקשת של מתכון. אם תידרש לכתוב מתכון תקין עבורי, תצטרך לכתוב אותו ברמת פירוט גבוהה יותר. יש גם כל מיני פעולות בסיסיות שבהן לא תוכל להשתמש. 1 הכנס כאן תיאור חלופי לבחירתך. |
|
|
|
|
|
|
||
|
||||
|
1 אפילו ברמה הלוגית לא בדיוק ברור לי מה אתה מצפה ומאיזה מגבלות ישחרר אותך הרכיב הנ"ל. אבל אולי זה בגלל המוח המוגבל שלי. | |
|
|
|
|
|
||
|
||||
|
בקיצור: אין שום הוכחה שכל מודל חישוב אפשרי שקול למכונת טיורינג. הדבר היחידי שאנחנו יודעים הוא שכל מודל חישוב שאנחנו יכולים לממש או אפילו יכולים לתאר שקול לה. מכאן "מסיקים" באינדוקציה (של פיזיקאים) שכל מודל חישוב שקול לה. | |
|
|
|
|
|
||
|
||||
|
סליחה על הניטפוק, אבל זה קצת נשמע כמו טאוטולוגיה, ''כל מודל חישוב שאנחנו יכולים לממש או אפילו יכולים לתאר שקול לה'', כאילו בזאת הגדרת מהו מודל חישוב. | |
|
|
|
|
|
||
|
||||
|
לא טאוטולוגיה (אבל לא משהו חכם במיוחד) - לכל מודל חישוב מעשי שהוצע, הודגם שהוא יכול להיות ממומש על ידי מכונת טיורינג. | |
|
|
|
|
|
||
|
||||
|
לא נכון. מכונת טיורינג לא יכולה להנפיק סדרה אקראית ויש מכשירים ש(על פי התיאוריה הפיזיקלית) יכולים. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |