היא השאלה אם קיים אלגוריתם כללי שיקבע מראש אם תוכנית תסתיים אי פעם או תרוץ לנצח, והיא מיוחסת כמעט תמיד למאמרו של טיורינג מ־1936. מחקר לוגי־היסטורי חזר אל המאמר עצמו. מה בדיוק כתוב בו?
מחקר לוגי־היסטורי מ־2024 מראה שזה לא מדויק: טיורינג בנה שם את מלוא התשתית הנדרשת, כולל ורעיון המחשב האוניברסלי, והוכיח אי־כריעות של כמה בעיות דומות, אך הניסוח הספציפי של "בעיית העצירה" כפי שהוא נלמד היום מעולם לא הופיע במאמר במפורש.
המאמר מ־1936 נחשב לאבן היסוד של מדעי המחשב, וזה אינו מוטל בספק. בתוכו מוגדרת מכונת טיורינג, מוצג רעיון המכונה האוניברסלית שמריצה תיאור של מכונה אחרת, ומוכחת אי־כריעות של כמה בעיות.
מה שהמחקר מ־2024 בודק הוא צר וספציפי: האם הניסוח המוכר של בעיית העצירה, כפי שהוא מופיע בכל ספר לימוד, מופיע שם. הבדיקה נעשתה בהשוואה מסודרת בין מה שטיורינג ניסח והוכיח בפועל לבין מה שמצוטט בשמו.
המסקנה היא שהניסוח הזה אינו במאמר. הבעיות שטיורינג הוכיח קרובות מאוד ומנוסחות אחרת, והתשתית כולה נמצאת שם, והניסוח המדויק התגבש מאוחר יותר, כשהתחום נכנס לספרי לימוד ונדרש להצגה נקייה.
חשוב לא להפוך את זה למה שאינו. אין כאן טענה שטיורינג לא תרם או שמישהו אחר הוכיח, אלא דיוק בייחוס. והלקח כללי יותר: גם ייחוס שנשמע מובן מאליו שווה בדיקה מול המקור, מפני שסיפור שמסופר מחדש נוטה להתיישר ולהתקצר.
wat. הניסוח המדויק של "בעיית העצירה" שמלמדים בכל קורס מדעי המחשב לא מופיע במאמר של טיורינג.
wat wat
זו תזכורת לכך שגם בסיסי ומוכר ככל שיהיה כדאי לבדוק מול המקור המקורי, ולא להסתמך על האופן שבו הם מסופרים מחדש שוב ושוב.
איך יודעים?
המחקר משווה בקפידה בין הטענות שטיורינג ניסח והוכיח בפועל במאמר המקורי לבין הניסוח המודרני שמיוחס לו בספרי לימוד, ומצביע על הפער בין השניים.
מה עדיין לא יודעים?
המחקר לא טוען שטיורינג לא תרם ליסודות הבעיה, אלא רק שהניסוח המדויק שמיוחס לו במפורש לא נמצא במאמר עצמו, וזו ולא ביטול התרומה.
למדתם משהו?
מכאן ממשיכים
האם יש אמת מתמטית שאי אפשר להוכיח?לוגיקה
איך יודעים בוודאות ששני אנשים בלונדון חולקים אותו מספר שערות?הוכחה
כמה צבעים צריך כדי לצבוע כל מפה בעולם?הוכחה