בתשובה לירדן ניר-בוכבינדר, 11/02/13 22:55
האם ניתן להוכיח שאלגוריתם שקול למכונת טיורינג? 612409
ויש עוד הערה מתחייבת:

המילה "אלגוריתם" כשלעצמה לא מגדירה מהם הצעדים הבסיסיים שבהם הוא יכול להשתמש. אם הייתה אפשרות למיישם האלגוריתם היכולת ההיפותטית להשתמש בצעד הבסיסי "פתור משוואה דיופונטית", היה אלגוריתם פשוט מאוד לפתור משוואה דיופונטית. אבל במובן הרחב הזה הבעיה פשוטה וחסרת משמעות.
QED - לא מה שחשבת שהוכחת 612449
תקן אותי אם אני טועה, אבל בעולם המחשוב היום (וגם במכונת טיורינג מן הסתם) די ברור מהם הצעדים הבסיסיים, והם מאד מאד בסיסיים באמת‏1. וכמובן שכל הגדרת צעד סבוך יותר ניתנת לפרישה רקורסיבית, כשבתור 'אלגוריתם' תוכל להגדיר רק אלגוריתם שנפרש (ופורש למעשה) עד תומו‏2.

1 משהו כמו כל מה שאפשר לעשות עם שני ביטים, פלוס כתיבה לכתובת וקפיצה לכתובת, אתה בטח יודע את זה יותר טוב ממני.

2 זה מזכיר לי אסוציאטיבית את התיאור של פיינמן לאלקטרודינמיקה קוונטית, מתוך ספרו המאד מומלץ שסיימתי לקרוא (שוב) לאחרונה: QED - The strange theory of light and matter. בספר הזה, שהוא ספר מדע פופולרי ולכן לא משתמש בשום משוואות ('אלגוריתמים') מסובכות, הוא טוען ומסביר שכל מה שעושים בתורה הנ"ל, מתמצה בסיכום ארוך ומפרך של אמפליטודות ופאזות (או חצים קטנים בזוויות שונות אם נדייק בתיאורו). ואז הוא אומר שמה שלוקח לסטודנטים שלו 3 שנים של קורסי דוקטורט, זה ללמוד את האלגוריתמים היותר מסובכים שעושים את זה ביעילות - אינטגרלי מסלול וחיות אחרות (אנלוגי ל"פתור משוואה דיופנטית" שלך).

הספר, אגב, בהחלט נמצא בשלישייה הראשונה של ספרי המדע הפופולרי שקראתי, ומומלץ בחום רב לכל מי שמתעניין בתורת הקוונטים (+) ומה שיש לה להגיד על פוטונים, אלקטרונים ומה שביניהם, שכמו שפיינמן אומר, מכסה לא רע את רוב התופעות שאנו חווים ביום-יום, מלבד כבידה כמובן.
QED - לא מה שחשבת שהוכחת 612450
בהתחלה רציתי לכתוב על ההערה שלי שהיא הערה נוקדנית (ניטפוק בעברית). אני חושב שמה שכתבת מובן בהחלט לכל מי שקצת מכיר את התחום ונכון אם אנחנו רוצים לייחס משמעות מועילה למונח הזה. אולם בעיקרון אין שום הבטחה תיאורטית שעוד חמש שנים לא יומצא איזה רכיב חישוב מופלא שמסתמך על המימדים המקופלים של תורת המיתרים‏1 ומצליח לשחרר אותנו ממגבלותיה של מכונת טיורינג.

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

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

1 הכנס כאן תיאור חלופי לבחירתך.
QED - לא מה שחשבת שהוכחת 612455
1 אפילו ברמה הלוגית לא בדיוק ברור לי מה אתה מצפה ומאיזה מגבלות ישחרר אותך הרכיב הנ"ל. אבל אולי זה בגלל המוח המוגבל שלי.
QED - לא מה שחשבת שהוכחת 612478
בקיצור: אין שום הוכחה שכל מודל חישוב אפשרי שקול למכונת טיורינג. הדבר היחידי שאנחנו יודעים הוא שכל מודל חישוב שאנחנו יכולים לממש או אפילו יכולים לתאר שקול לה. מכאן "מסיקים" באינדוקציה (של פיזיקאים) שכל מודל חישוב שקול לה.
QED - לא מה שחשבת שהוכחת 612481
סליחה על הניטפוק, אבל זה קצת נשמע כמו טאוטולוגיה, ''כל מודל חישוב שאנחנו יכולים לממש או אפילו יכולים לתאר שקול לה'', כאילו בזאת הגדרת מהו מודל חישוב.
QED - לא מה שחשבת שהוכחת 612482
לא טאוטולוגיה (אבל לא משהו חכם במיוחד) - לכל מודל חישוב מעשי שהוצע, הודגם שהוא יכול להיות ממומש על ידי מכונת טיורינג.
QED - לא מה שחשבת שהוכחת 612486
לא נכון. מכונת טיורינג לא יכולה להנפיק סדרה אקראית ויש מכשירים ש(על פי התיאוריה הפיזיקלית) יכולים.

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

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