תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
←‏משפט הרדוקציה: תיקנתי שגיאה בסעיף משפט הרדוקציה
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד
שורה 80:
}}
 
במילים אחרות, אם השפה <math>L_2</math> שייכת למחלקה כלשהי, גם השפה <math>L_1</math> שייכת לאותה מחלקה. באופן אינטואיטיבי, העובדה ש־<math>L_2</math> שייכת למחלקהלאחת מסויימתמן המחלקות הללו משמעותה שקיימת מ״ט מסויימת (לפי ההגדרה המתאימה של המחלקה) שמכריעה או מזהה אותה. עקב קיומה של פונקצית הרדוקציה, ניתן לבנות מ״ט שראשית ממירה קלט של <math>L_1</math> לקלט של <math>L_2</math> (ע״י חישוב הפונקציה f), ואח״כ מריצה את המכונה של <math>L_2</math> על מנת לפתור את הבעיה <math>L_1</math>. כעת נוכיח רעיון זה באופן פורמלי:
{{הוכחה|
נניח שקיימת רדוקציה f מ־<math>L_1</math> ל־<math>L_2</math> והיא ניתנת לחישוב ע״י מ״ט <math>M_f</math>.