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

תוכן שנמחק תוכן שנוסף
Atavory (שיחה | תרומות)
Atavory (שיחה | תרומות)
שורה 73:
#אם f היא רדוקציה מ־<math>L_1</math> ל־<math>L_2</math> אז אותה הפונקציה f היא גם רדוקציה מ־<math>\overline{L_1}</math> ל־<math>\overline{L_2}</math>. (נובע מהגדרת הרדוקציה)
 
==משפטים==
==משפט הרדוקציה==
 
={{משפט|שם=משפט הרדוקציה=|תוכן=
אם <math>L_1, L_2</math> שפות מעל <math>\Sigma</math> כך שקיימת רדוקציה <math>L_1 \le L_2</math> אזי:
# <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>. כעת נוכיח רעיון זה באופן פורמלי:
שורה 86 ⟵ 89:
:על קלט x, המכונה <math>M_1</math> מריצה את <math>M_f</math> (הפיכת הקלט x לקלט שמתאים ל־<math>L_2</math>), ומריצה את <math>M_2</math> על הקלט המומר. המכונה מחזירה את אותה התשובה שהחזירה <math>M_2</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\notin R</math>. אם <math>L_2\in R</math> נובע ממשפט הרדוקציה שהוכחנו לעיל שגם <math>L_1\in R</math>, וזו סתירה.