שיחה:תורת החישוביות/מודל לבעיות הכרעה

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

שקילות למודל הכללי[עריכה]

אינני רואה היכן יש צורך ב לצורך הגדרה זו.Atavory - שיחה 22:32, 21 בינואר 2012 (IST)

קיימים שני מודלים – כדי להראות שהם שקולים, חייבים להראות מיפוי מהאחד לשני (וחזרה). היא התמונה של f כשממפים מהמודל הכללי, למודל בעיות ההכרעה. איך ניתן להמנע מהגדרה זו? ‏gran‏ - שיחה 22:39, 21 בינואר 2012 (IST)
אין בעיה, פשוט בקטע זה, לאחר הגדרת , הוא אינו מופיע יותר. חשבתי שכדאי או להדגיש את השקילות דרכו, או להפטר מההגדרה ולהסביר דרך מילים בלבד. מה דעתך?Atavory - שיחה 22:56, 21 בינואר 2012 (IST)
לא רואה סיבה לשנות.. עדיף להיות פורמלי, גם אם לאחר מכן לא משתמשים בהגדרה זו יותר. ‏gran‏ - שיחה 23:08, 21 בינואר 2012 (IST)
אנא ראה את השינוי שהכנסתי. נראה לי שהשקילות המקורית שהופיעה היתה חלשה יחסית, במובן זה שהרדוקציה מM לM' היתה במובן "אם היינו יודעים לפתור את כל הבעיות מסוג זה" (כלומר ללא תלות בf). הפכתי את הרדוקציה לקונסטרוקטיבית (וקצת יותר מדוייקת).Atavory - שיחה 12:55, 22 בינואר 2012 (IST)