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