תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
תכונות |
|||
שורה 48:
*משני אלו נובעת התקפות של הרדוקציה. קל לראות שזו פונקציה מלאה וניתנת לחישוב ע״י מ״ט (כל שהמכונה נדרשת לעשות הוא החלפת הקידוד של מעבר ל־<math>q_{rej}</math> במעבר אחר).
==תכונות הרדוקציה==
# לכל שפה L, מתקיים <math>L \le L</math> ע״י פונקציית הזהות.
# אם f היא רדוקציה מ־<math>L_1</math> ל־<math>L_2</math>, ו־g היא רדוקציה מ־<math>L_2</math> ל־<math>L_3</math>, אזי ההרכבה <math>g\circ f</math> היא רדוקציה מ־<math>L_1</math> ל־<math>L_3</math>. (זוהי תכונת '''טרנזיטיביות''')
<center><math>L_1 \le L_2, L_2 \le L_3 \; \Rightarrow \; L_1 \le L_3</math></center>
#אם 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> אזי:
# <math>L_2 \in R \Rightarrow L_1 \in R</math>
# <math>L_2 \in RE \Rightarrow L_1 \in RE</math>
# <math>L_2 \in coRE \Rightarrow L_1 \in coRE</math>
במילים אחרות, אם השפה <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>L_1</math> ל־<math>L_2</math> והיא ניתנת לחישוב ע״י מ״ט <math>M_f</math>.
<math>L_2 \in R</math> אזי קיימת מ״ט <math>M_2</math> המכריעה את <math>L_2</math>. נבנה מ״ט <math>M_1</math> המכריעה את <math>L_1</math>:
:על קלט 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> אזי,
#<math>L_1 \notin R \; \Rightarrow\; L_2 \notin R</math>
#<math>L_1 \notin RE \; \Rightarrow\; L_2 \notin RE</math>
#<math>L_1 \notin coRE \; \Rightarrow\; L_2 \notin coRE</math>
הסבר: נניח ש־<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> אל אותן השפות. בד״כ ביצוע רדוקציה היא פעולה פשוטה בהרבה מאשר הוכחה ישירה ששפה אינה כריעה. [[../שפות שאינן כריעות|בפרק הבא]] נוכיח ששפה מסויימת אינה כריעה ונבצע רדוקציה ממנה למגוון שפות נוספות.
| |||