תורת החישוביות/כריעות שפות/רדוקציה חישובית: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←תכונות בסיסיות של רדוקציות: עיצוב |
מ ←משפטים: עיצוב, הגהה, להשלים: הוכחת שפה האלכסון. |
||
שורה 71:
#אם 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> אזי:{{רווח קשיח|4}}
# <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>
שורה 91:
ההוכחות עבור סעיפים 2 ו־3 דומות להוכחה לעיל. במקרה זה ייתכן ש־<math>M_2</math> לא עוצרת על קלטים מסויימים, וגם <math>M_1</math> לא תעצור על אותם הקלטים. אבל אלו יהיו בדיוק הקלטים עליהם מותר ל־<math>M_1</math> לא לעצור, לפי ההגדרה המתאימה של <math>RE</math>, <math>coRE</math>.
המשפט לעיל מענין דווקא בגלל הכיוון ההפוך שלו:
{{משפט|שם=משפט הרדוקציה
נניח <math>L_1\le L_2</math> אזי,
#<div class="mw-content-ltr"><math>L_1 \notin R \; \Rightarrow\; L_2 \notin R</math></div>
שורה 101:
הסבר: נניח ש־<math>L_1\notin R</math>. אם <math>L_2\in R</math> נובע ממשפט הרדוקציה שהוכחנו לעיל שגם <math>L_1\in R</math>, וזו סתירה.
משפט זה שימושי ביותר להראות ששפות אינן כריעות. מספיק להוכיח ששפה
<!--
להלן מספר דוגמאות להוכחת אי כריעותן של מספר שפות שראינו ב[[תורת החישוביות/כריעות שפות#כריעות למחצה חיובית|כריעות למחצה חיובית]]. -->▼
===שימושים במשפט הרדוקציה===
ראשית, נראה כי שפה מסויימת, שפת האלכסון, אינה כריעה. לאחר מכן, נראה שרשרת רדוקציות לשפות אחרות. ממשפט הרדוקציה (ההפכי) ינבע שכלל השפות אינן כריעות.
{{להשלים|הוכחה שמשלים הלאכסון לא כריעה}}
נשים לב ש־<math>R</math> סגורה למשלים. לפיכך, מכיוון ש־<math>\overline{L_D} \notin R</math>, כך גם השפה המשלימה <math>L_D \notin R</math>.▼
▲להלן מספר דוגמאות להוכחת אי כריעותן של מספר שפות שראינו ב[[תורת החישוביות/כריעות שפות#כריעות למחצה חיובית|כריעות למחצה חיובית]].
כעת נראה ששאר השפות שראינו בפרק [[תורת החישוביות/כריעות שפות#כריעות למחצה חיובית|כריעות למחצה חיובית]] אינן כריעות.
#'''אי כריעות השפה האוניברסלית''' – ראינו מקודם שמתקיים <math>L_D \le L_U</math>. ממשפט הרדוקציה ההפכי, נובע שבגלל ש־<math>L_D \notin R</math> אז גם <math>L_U \notin R</math>.
#'''אי כריעות שפת בעיית העצירה''' – ראינו מקודם שמתקיים <math>L_U \le L_\text{HP}</math>. ממשפט הרדוקציה ההפכי, נובע שבגלל ש־<math>L_U \notin R</math> אז גם <math>L_\text{HP} \notin R</math>.
{{תרגיל|יישור=ימין|שאלה=סווג את השפות הבאות למחלקה המתאימה (<math>R, RE\smallsetminus R, coRE\smallsetminus R</math> או מחוץ ל־<math>RE\cup coRE</math>):
▲נשים לב ש־<math>R</math> סגורה למשלים. לפיכך, מכיוון ש־<math>\overline{L_D} \notin R</math>, כך גם השפה המשלימה.
* <math>L_D, L_U, L_{HP}, \overline {L_D}, \overline{L_U}, \overline {L_\text{HP}}</math>
}}
לסיום, נראה שפה ספציפית שאינה ב־<math>RE\cup coRE</math>:
{{להשלים}}
{{תורת החישוביות|מוגבל}}
| |||