מה לא יכול המחשב לעשות

בתשובה לאורי גוראל-גורביץ', 17/12/06 23:41

ההוכחה הזאת פשוט דבילית

425003

גדי אלכסנדרוביץ' • בתשובה לאורי גוראל-גורביץ'

יום א', 17/12/2006, 23:59

זה דומה למשהו שכבר אמרתי במקום אחר: נניח שאנחנו רוצים לפתור את בעית העצירה עבור מכונה M וקלט x, ויש לנו Q שמכריע אותה עבור מכונות שלא מקבלות קלט. אני בונה מכונה Mx שלא מקבלת קלט ומה שהיא עושה הוא לכתוב על הסרט שלה את x ואז להריץ את M, ומעביר אותה ל-Q.

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

ההוכחה הזאת פשוט דבילית

425005

אורי גוראל-גורביץ' • בתשובה לגדי אלכסנדרוביץ'

יום ב', 18/12/2006, 0:07

תמיד יש את הבעיה הזו כשמשלימים דיונים עם עשרות+ תגובות: או שתגיב ותחרמופף או שתקרא קודם את הכל ותשכח על מה רצית להגיב.

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

המאמר המלא

מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
RSS מאמרים \| כתבו למערכת \| אודות האתר \| טרם התעדכנת \| ארכיון \| חיפוש \| עזרה \| תנאי שימוש	© כל הזכויות שמורות