בתשובה לגדי אלכסנדרוביץ', 15/12/06 18:03
ההוכחה הזאת פשוט דבילית 424999
אורי גוראל-גורביץ' • בתשובה לגדי אלכסנדרוביץ' יום א', 17/12/2006, 23:41
הנה שאלה ש(עוד) לא מיצתה את עצמה: הוכח שאי אפשר להכריע את בעית העצירה בקבוצת כל מ"ט שלא מקבלות קלט.
ההוכחה הזאת פשוט דבילית 425003
גדי אלכסנדרוביץ' • בתשובה לאורי גוראל-גורביץ' יום א', 17/12/2006, 23:59
זה דומה למשהו שכבר אמרתי במקום אחר: נניח שאנחנו רוצים לפתור את בעית העצירה עבור מכונה M וקלט x, ויש לנו Q שמכריע אותה עבור מכונות שלא מקבלות קלט. אני בונה מכונה Mx שלא מקבלת קלט ומה שהיא עושה הוא לכתוב על הסרט שלה את x ואז להריץ את M, ומעביר אותה ל-Q.

אבל הרדוקציה הפרטנית הזו די מיותרת, כי משפט רייס (שלא הוזכר במאמר) כולל גם את המקרה הזה.
ההוכחה הזאת פשוט דבילית 425005
אורי גוראל-גורביץ' • בתשובה לגדי אלכסנדרוביץ' יום ב', 18/12/2006, 0:07
תמיד יש את הבעיה הזו כשמשלימים דיונים עם עשרות+ תגובות: או שתגיב ותחרמופף או שתקרא קודם את הכל ותשכח על מה רצית להגיב.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות