תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←משפט הרדוקציה: הגהה |
|||
שורה 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> על הקלט המומר.
ההוכחות עבור סעיפים 2 ו־3 דומות להוכחה לעיל. במקרה זה ייתכן ש־<math>M_2</math> לא עוצרת על קלטים מסויימים, וגם <math>M_1</math> לא תעצור על אותם הקלטים. אבל אלו יהיו בדיוק הקלטים עליהם מותר ל־<math>M_1</math> לא לעצור, לפי ההגדרה המתאימה של RE, coRE.
אם נביט במשפט ההפכי למשפט הרדוקציה לעיל, נקבל את המשפט הבא:
#<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>, וזו סתירה.
|