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

# <div class="mw-content-ltr"><math>L_2 \in R \Rightarrow L_1 \in R</math></div>

# <div class="mw-content-ltr"><math>L_2 \in RE \Rightarrow L_1 \in RE</math></div>

# <div class="mw-content-ltr"><math>L_2 \in coRE \Rightarrow L_1 \in coRE</math></div>

במילים אחרות, אם השפה <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>f(x)</math> יסתיים לכל קלט x, ובגלל ש־<math>M_2</math> מכריעה (כלומר, עוצרת על כל קלט) גם המכונה <math>M_1</math> עוצרת לבסוף על כל קלט. כמו כן, f <u>תקפה</u>, כלומר <math>x\in L_1</math> אם״ם <math>f(x)\in L_2</math>. ולכןלכן אם <math>x\in L_1</math> אז הקלט המומר <math>f(x)\in L_2</math>, ו־<math>M_2</math> תקבל את הקלט. מכאן שבמקרה ומכאןזה ש־<math>M_1</math> מקבלת את x. מצד שני, אם <math>x\notin L_1</math> אזי <math>f(x)\notin L_2</math> ולכן <math>M_2</math> דוחה את הקלט המומר, וגם <math>M_1</math> דוחה כנדרש. מכאן נובע – <math>M_1</math> מכריעה את <math>L_1</math> ולכן ו־<math>L_1\in R</math> לפי ההגדרה.}}

ההוכחות עבור סעיפים 2 ו־3 דומות להוכחה לעיל. במקרה זה ייתכן ש־<math>M_2</math> לא עוצרת על קלטים מסויימים, וגם <math>M_1</math> לא תעצור על אותם הקלטים. אבל אלו יהיו בדיוק הקלטים עליהם מותר ל־<math>M_1</math> לא לעצור, לפי ההגדרה המתאימה של RE/, coRE.

אם נביט במשפט ההפכי למשפט הרדוקציה לעיל, נקבל את המשפט הבא: {{ש}}נניח <math>L_1\le L_2</math> אזי,

#<div class="mw-content-ltr"><math>L_1 \notin R \; \Rightarrow\; L_2 \notin R</math></div>

#<div class="mw-content-ltr"><math>L_1 \notin RE \; \Rightarrow\; L_2 \notin RE</math></div>

#<div class="mw-content-ltr"><math>L_1 \notin coRE \; \Rightarrow\; L_2 \notin coRE</math></div>

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