בתשובה לגדי אלכסנדרוביץ', 14/12/06 13:36
בעית העצירה 424532
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 16:50
לא מוצא Wang tiling, אבל ברור שהמשוואות הדיופנטיות הן פשוט מקרה פרטי של בעית העצירה. בעית העצירה עדין נראית לי כמו בעיה מיוחדת (לכל הפחות, הברורה ביותר מתוך מחלקת בעיות שקולות).
בעית העצירה 424557
גדי אלכסנדרוביץ' • בתשובה לעדי סתיו יום ה', 14/12/2006, 19:51
טוב, יש בויקיפדיה האנגלית:
ושווה גם להזכיר את משפט רייס:

משפט רייס [ויקיפדיה]

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

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

כמובן שיש קשר בין משפט רייס ובעיית העצירה - מוכיחים אותו על ידי כך שעושים רדוקציה מבעיית העצירה לבעייה של בחינת התכונה הלא טריוויאלית.
בעית העצירה 424562
עדי סתיו • בתשובה לגדי אלכסנדרוביץ' יום ה', 14/12/2006, 20:03
רייס בהנדסת תוכנה מסחרית זה ''עבור כל בעיה תכנותית, יש מימוש שבאמת אף-אחד לא יכול להבין''. שאל כל מתכנת.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות