תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ תורת החישוביות/כריעות שפות/רדוקציה הועבר לתורת החישוביות/כריעות שפות/רדוקציה חישובית: סידור לפני איחוד |
מ קישורים פנימיים |
||
שורה 103:
הסבר: נניח ש־<math>L_1\notin R</math>. אם <math>L_2\in R</math> נובע ממשפט הרדוקציה שהוכחנו לעיל שגם <math>L_1\in R</math>, וזו סתירה.
משפט זה שימושי ביותר להראות ששפות אינן כריעות. מספיק להוכיח ששפה מסויימת <math>L_1</math> אינה כריעה (כלומר, אינה ב־R), ובעזרתה נוכל להוכיח ששפות אחרות אינן כריעות ע״י רדוקציה מ־<math>L_1</math> אל אותן השפות. בד״כ ביצוע רדוקציה היא פעולה פשוטה בהרבה מאשר הוכחה ישירה ששפה אינה כריעה. [[../קיום שפות שאינן כריעות|בפרק הבא]] נוכיח ששפה מסויימת אינה כריעה ונבצע רדוקציה ממנה למגוון שפות נוספות.
| |||