ויקיספר

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Gran (שיחה | תרומות)
2,595 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
שילוב זמני
שורה 2:
 
[[w:משפט רייס|משפט רייס]]
טוען שבהנתן קידוד של מ״ט <math>\langle M \rangle</math>, קשה לדעת מההאם השפה <math>L(M)</math> שהמכונהמקיימת מכריעהתכונה לא-טריוויאלית כלשהי (מושג שנגדירו במדוייק בהמשך). זהו כלי עזר חזק בהוכחה שבעיות אינן כריעות או אפילו נתנות למניה רקורסיבית.
 
המשפט מגדיר משפחות של שפות <math>S</math> – כל שפה <math>L\in S</math> היא אוסף מכונות טיורינג שהשפה שהן מכריעות מקיימת '''תכונה''' מסויימת, למשל, השפה שהן מכריעות היא ריקה, או השפה שהן מכריעות מכילה מספר זוגי של מילים, וכו'. המשפט מראה שאם התכונה הנ״ל אינה טריוויאלית, אז השפה <math>L</math> (שהיא, כאמור, אוסף קידודי מכונות הטיורינג ששפתן מקיימות את התכונה האמורה) אינה כריעה.
ב[[#תכונות של שפות|תכונות של שפות]] נגדיר במדוייק מהן תכונות של שפות, ובפרט מהן תכונות לא-טריוויאליות שלהן. ב[[#משפט רייס|משפט רייס]] נוכיח שההחלטה האם לשפת המ"ט ישנה תכונה כזו - איננה כריעה. ב[[#דוגמאות ליישומי משפט רייס|דוגמאות ליישומי משפט רייס]] נראה דוגמאות לשימוש נכון ושגוי במשפט. ב[[#מניה רקורסיבית של שפות בעלות תכונה|מניה רקורסיבית של שפות בעלות תכונה]] נוכיח שההחלטה האם לשפת המ"ט יש תכונה לא טריוויאלית - בעקרון איננה אפילו נתנת למניה רקורסיבית (ונדון במקרים מיוחדים בהם היא כן).
 
 
==תכונות של שפות==
שורה 38 ⟵ 40:
לכל תכונה לא טריוויאלית S של שפות ב־RE מתקיים:{{רווח קשיח|10}} <math>L_S \notin R</math>{{רווח קשיח|10}}}}
{{הוכחה|1=
נראה כי <math>L_S \notin R</math> על־ידי הרדוקציה <math>\text{HP} \le L_S</math>. מכיוון שראינו ש־<math>\text{HP}\notin R</math> נובע המשפט.
 
נראה כי <math>L_S \notin R</math> על־ידי הרדוקציה <math>\text{HP} \le L_S</math>. כלומר, נניח על דרך השלילה <math>L_S \in R</math>, ונראה כי אפשר להכריע לכל מ"ט <math>M</math> וקלט <math>x</math>, האם <math>M</math> עוצרת על <math>x</math> ((מה ש[[תורת_החישוביות/כריעות_שפות/שפות_שאינן_כריעות#שפות_שאינן_כריעות|ידוע שאינו נכון]]).
נניח כי ה[[אוטומטים ושפות פורמליות/שפות פורמליות|שפה הריקה]] אינה ב־<math>S</math> (כלומר▼
 
▲בלי הגבלת הכלליות, נניח כי ה[[אוטומטיםתורת ושפות פורמליותהחישוביות/שפותכריעות פורמליותשפות|שפה הריקה]] אינה ב־<math>S</math> (כלומר
<math>\emptyset \notin S</math>).
במקרה זהאחרת, פשוט נוכיח את המשפט לגבי התכונה המשלימה <math>\overline S</math> –- ▼
היות ש־<math>S</math> אינה טריוויאלית, בהכרח קיימת שפה <math>L_0</math> כך ש־<math>L_0 \in S</math>. מכיוון ש־<math>S</math> היא קבוצה של שפות ב־<math>RE</math>, גם <math>L_0 \in RE</math>, ונניח כי <math>M_0</math> היא מ״ט המקבלת אותה.▼
כפי שראינו לעיל, גם המשלים של תכונה לא-טריוויאלית הוא תכונה לא טריוויאלית, והכרעה רקורסיבית לגבי <math>S</math> שקולה להכרעה רקורסיבית לגבי <math>\overline S</math>. באופן פורמלי,▼
 
 
▲היות ש־ש-<math>S</math> אינה טריוויאלית, בהכרח קיימת שפה <math>L_0</math> כך ש־<math>L_0 \in S</math>. מכיוון ש־<math>S</math> היא קבוצה של שפות ב־<math>RE</math>, גם <math>L_0 \in RE</math>, ונניח כי <math>M_0</math> היא מ״טהמ"ט המקבלת אותה.
 
נגדיר את הרדוקציה ע"י מ"ט <math>f(\langle M \rangleM_x</math>, x)הפועלת =כך. \langleבנהתן M_xקלט \rangle<math>w</math>, באופןהמ"ט הבא.<math>M_x</math>:
בהנתן קלט <math>w</math>, המ"ט <math>M_x</math>:
# מריצה את <math>M</math> על <math>x</math> (ומתעלמת מהתוצאה, אם יש), ואז
# מריצה את <math>M_0</math> על <math>w</math>, ומקבלת/דוחה כמותה
(הערה: אם הקלט אינו <math>(\langle M \rangle, x)</math> פלט הפונקציה f מוגדר בתור מ״ט הדוחה כל קלט (באופן זה השפה של מכונה הפלט הוא <math>L(M)=\emptyset \notin S</math>)
 
כעת נראה ש־f מקיימת את תכונות הרדוקציה כפי שהגדרנו בפרק [[תורת החישוביות/כריעות שפות/רדוקציה|רדוקציה]]:
#f פונקציה מלאה: הגדרנו את f לכל קלט אפשרי
# f פונקציה ברת־חישוב: ייצור <math>\langle M_X \rangle</math> מתוך המחרוזת <math>(\langle M \rangle, x)</math> ומתוך המחרוזת הקבועה <math>\langle M_0\rangle</math> קל לביצוע ע״י מ״ט שצריכה רק לשנות מעט את קידודי המכונות כדי שירוצו אחת אחר השניה...
# f רדוקציה תקפה:
#* אם M לא עוצרת על x, גם <math>M_x</math> לא עוצרת. <math>L(M_x) = \emptyset \notin S</math>▼
#* אם M עוצרת על x{{כ}}, <math>M_X</math> מתנהגת בדיוק כמו <math>M_0</math>{{כ}}, <math>L(M_x)=L(M_0)\in S</math>▼
#: לפיכך
#:: אם <math>(\langle M \rangle, x)\in\text{HP}</math> אז M עוצרת על x, ומתקיים <math>L(M_x)=L_0\in S</math>, ולכן <math>\langle M_x\rangle \in L_S</math>
#:: אם <math>(\langle M \rangle, x)\notin\text{HP}</math> אז M לא עוצרת על x, ומתקיים <math>L(M_x)=\emptyset\notin S</math>, ולכן <math>\langle M_x\rangle \notin L_S</math>
 
מהנחתנו בשלילה ש-<math>L_S \in R</math>, נובע שיש מ"ט רקורסיבית <math>Q</math> המכריעה זאת. כדי להכריע האם <math>M</math> עוצרת על <math>x</math>, נשאל את <math>Q</math> האם <math>M_x \in L_S</math>:
לסיום, הנחנו לעיל ש־<math>\emptyset \notin S</math>, אך מה קורה אם הנחה זו אינה נכונה?
▲#* אם <math>M</math> לאאיננה עוצרת על <math>x</math>, אז גם <math>M_x</math> לאאיננה עוצרת על אף <math>w</math>. אם כך, <math>L(M_x) = \emptyset \notin S</math>, ו-<math>Q</math> תכריע ש-<math>M_x \notin L_S</math>.
▲במקרה זה, פשוט נוכיח את המשפט לגבי התכונה המשלימה <math>\overline S</math> –
▲#* אם <math>M</math> עוצרת על x{{כ}}, אז <math>M_X</math> מתנהגת בדיוק כמו <math>M_0</math>{{כ}}. אם כך, <math>L(M_x)=L(M_0)\in S</math>, ו-<math>Q</math> תכריע ש-<math>M_x \in L_S</math>.
▲כפי שראינו לעיל, גם המשלים של תכונה לא-טריוויאלית הוא תכונה לא טריוויאלית, והכרעה רקורסיבית לגבי <math>S</math> שקולה להכרעה רקורסיבית לגבי <math>\overline S</math>. באופן פורמלי,
נביט בתכונה המשלימה <math>\overline S = RE \smallsetminus S</math>. מתקיים <math>\emptyset \notin \overline{S}</math> ולכן, כפי שהוכחנו <math>L_{\overline{S}}\notin R</math>. נשים לב ש
<center><math>L_{\overline{S}}=\{\langle M\rangle \mid L(M) \in \overline S\} = \{\langle M\rangle \mid L(M) \notin S\} = \overline{L_S}</math></center>
כלומר <math>\overline {L_S} \notin R</math>, ומכיוון ש־R סגורה למשלים, זו הוכחה ש־<math>L_S \notin R</math> כנדרש.
}}▼
 
נשים לב שהרדוקציה אכן ברת חישוב - בהנתן <math>(\langle M \rangle, x)</math>, קל לבנות פונקציה המשרשרת את שתי המכונות ויוצרת את תיאור <math>M_x</math>. כמו כן, לפי הנחתנו בשלילה, הקריאה ל<math>Q</math> מסתיימת גם כן.
למשפט רייס קיימת גם גרסא מורחבת:
▲}}
{{משפט|שם=משפט רייס המורחב|תוכן=
לכל תכונה לא טריוויאלית S של שפות ב־RE מתקיים:{{רווח קשיח|10}} <math>L_S \notin RE</math>{{רווח קשיח|10}}}}▼
 
==דוגמאות ליישומי משפט רייס==
שורה 81 ⟵ 72:
הבעיה היא
<center><math>
\text{Palindromes} = \{ \langle M \rangle \mid| \text{any palindrome} \in L(M) \}.
</math></center>
כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה
 
<center><math>
S_P = \{ L \mid| L \in RE \bigwedge \text{any palindrome} \in L \}.
</math></center>
כעת, בפורמט המתאים, נוכל לשים לב שמשפט רייס חל. התכונה איננה טריוויאלית: השפה (הנתנת למניה רקורסיבית)
שורה 106 ⟵ 97:
 
{{דוגמה|תוכן=
החלט האם הבעיה הבאה היא כריעה: נתון ייצוג של מ"ט <math>M</math>. האם אפשר לאפטם את <math>M</math> כך שזמן הריצה שלה בקבלת <math>x</math> יהיה תת־לינאריתת-לינארי ב־ב<math>|X|</math>, אורך הקלט שלה?
 
כדי להמיר זאת לפורמט מתאים לבעיית רייס, נכתוב את התכונה
 
<center><math>
S_P = \{ L \mid| L \in RE \bigwedge \exists_M \forall_x \; M \text{ accepts } x \text{ in } o(|x|) \text{ time} \}.
</math></center>
כעת אפשר לראות שמדובר בתכונה של שפות, הגם שהן מוגדרות ע"י מכונות טיורינג. המשך דוגמה זו מופיע ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים#אופטימיזציית מ"ט|תרגיל: אופטימיזציית מ"ט]].
שורה 122 ⟵ 113:
ב[[#משפט רייס|חלק קודם]] ראינו שאם התכונה <math>S</math> איננה טריוויאלית, אז שאלת השייכות ל-<math>L_S</math> איננה ב-<math>R</math>. בחלק זה נעסוק בשאלה מהם התנאים ל-<math>S</math> כך ששאלת השייכות ל-<math>L_S</math> תהיה ב-<math>RE</math>.
 
ללא תנאים נוספים, אם <math>S</math> תכונה לא טריוויאלית, אז שאלת השייכות ל-<math>L_S</math> איננה ב-<math>RE</math>. ב[[תורת החישוביות/כריעות שפות/משפט רייס/תרגילים#הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית|תרגיל: הכרעת תכונות לא-טריוויאליות איננה נתנת למניה רקורסיבית]] תתבקש להוכיח זאת.את המשפט הבא:
{{משפט|
▲לכלתוכן=באופן תכונהכללי, לאלתכונה לא-טריוויאלית <math>S</math> של שפות ב־RE מתקיים:{{רווח קשיח|10}} <math>L_S \notin RE</math>{{רווח קשיח|10}}}}
 
(דהיינו, ישנה שפה <math>S</math> שעבורה ההחלטה איננה ב-<math>RE</math>). }}
 
עם זאת, ישנם תנאים נוספים ל-<math>S</math>, שקיומם מהווה תנאי מספיק והכרחי לכך ששאלת השייכות היא ב-<math>RE</math>.
שורה 139 ⟵ 134:
 
נשים לב שמתנאי 3 נובע שישנה מכונה <math>Q_3</math> אשר בהנתן שפה סופית השייכת ל<math>S</math>, עוצרת בשלב כלשהו ומקבלת את השפה. המכונה <math>Q</math> משתמשת ב<math>Q_3</math>.
ש
 
המכונה <math>Q</math> פועלת במספר לולאות מקוננות:
# בלולאה החיצונית ביותר, היא מקדמת אינדקס <math>i = 0, 1, 2, \ldots</math>. עבור כל <math>i</math>, היא מייצרת את המחרוזת ה-<math>i</math> ב[[w:סדר לקסיקורפי|סדר לקסיקורפי]].
# בלולאה פנימית יותר, עבור ערך <math>i</math> והמחרוזת ה-<math>i</math>, היא מפעילה את <math>M</math> למשך <math>i</math> שלבים. אם המילה מתקבלת, <math>Q</math> מוסיפה אותה לרשימת מילים ש-<math>M</math> מקבלת.
# בלולאה פנימית יותר, עבוררשימתעבור רשימת המילים שהתקבלו ע"י <math>M</math> עד כה, המכונה <math>Q</math> מייצרת את כל תת-הקבוצות האפשריות של המילים שהתקבלו עד כה.
# בלולאה הפנימית ביותר, עבור ערך <math>i</math> ותת-קבוצה של מילים מתקבלות, המכונה <math>Q</math> מריצה את <math>Q_3</math> לשאול האם תת-הקבוצה שייכת ל<math>S</math>. אם כן, המכונה <math>Q</math> עוצרת בתשובה חיובית.
 
שורה 162 ⟵ 157:
 
{{תורת החישוביות|מוגבל}}
[[קטגוריה:תורת החישוביות]]
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/כריעות_שפות/משפט_רייס"