תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←דוגמאות לשפות בRE: נווט תחתון לתרגילים |
ארגון מחודש של החלק |
||
שורה 1:
{{תורת החישוביות}}
ב[[תורת החישוביות/מבוא#מוטיווציה|חלק המוטיווציה במבוא לספר]], ראינו שאי אפשר לכתוב תוכנית מחשב המזהה באופן כללי תוכנית מחשב כלשהי עוצרת כאשר היא מקבלת קלט כלשהו. בחלק זה נגדיר מושג זה ומושגים נלווים בצורה מדוייקת יותר, ונעסוק בתכונותיהם.
בפרק זה נראה שלוש מחלקות של בעיות. באופן לא מדוייק, ה[[#כריעות|שפות הכריעות]] הן משפחת השפות שאפשר לזהות באופן מלא, ואילו [[#כריעות למחצה חיובית|שפות כריעות למחצה חיובית]] ו[[#כריעות למחצה שלילית|שפות כריעות למחצה שלילית]] הן שפות שאפשר לזהות באופן חלקי.
בשאר חלקי הפרק נעסוק במחלקות אלו. הפרק [[תורת החישוביות/כריעות שפות/קיום שפות שאינן כריעות/ארגז חול|קיום שפות שאינן כריעות]] מראה שאכן יש שפות שאי אפשר לזהותן (כפי שראינו מעט ב[[תורת החישוביות/מבוא#מוטיווציה|חלק המוטיווציה במבוא]]). הפרקים [[תורת החישוביות/כריעות שפות/רדוקציה|רדוקציה]] ו[[תורת החישוביות/כריעות שפות/משפט רייס|משפט רייס]] מראים שתי טכניקות כלליות ביותר, שכ"א מהן יכולה לשמש להוכחה ששפה כלשהי נמצאת (או לא) באחת ממחלקות אלו. הפרק [[תורת החישוביות/כריעות שפות/אי-הפרדתיות רקורסיבית|אי-הפרדתיות רקורסיבית]] דן במאפיין נוסף של שפות במחלקות אלו.
==סוגי הכריעות ומחלקות הכריעות==
===כריעות (מלאה)===
אינטואיטיבית, שפה היא '''כריעה''' אם יש מכונת טיורינג העוצרת בוודאות על כל קלט, ומקבלת או דוחה בצורה נכונה האם הקלט שייך לשפה.
{{הגדרה|תוכן=
נאמר שמ"ט <math>M</math> '''מכריעה''' שפה <math>L</math> אם היא <u>מקבלת</u> כל מילה ב־<math>L</math> ו<u>דוחה</u> כל מילה שאינה ב־<math>L</math>. כלומר, <math>M</math> עוצרת על כל מילת קלט (אין מילים שגורמות למכונה להכנס ללולאה אינסופית).
שפה <math>L</math> '''ניתנת להכרעה''' אם קיימת מ"ט <math>M</math> שמכריעה אותה. שפה <math>L</math> '''אינה כריעה''' אם לא קיימת מ״ט <u>שמכריעה</u> אותה.
}}
{{דוגמה|תוכן=
להלן דוגמאות לשפות כריעות:
# השפה <math>\Sigma^*</math> – לכל קלט, בצעד החישוב הראשון המכונה עוברת ל־<math>q_{acc}</math>.
# השפה הריקה <math>\emptyset</math> – לכל קלט, המכונה עוברת בצעד החישוב הראשון ל־<math>q_{rej}</math>.
#כל שפה סופית <math>L=\{ a_1, a_2, \ldots, a_n \}</math> – נבדוק כל מילה אפשרית. מכיוון שכמות המילים סופית, נדרשים מספר סופי של מצבים (ובפרט, זו [[אוטומטים ושפות פורמליות/תכונות של שפות רגולריות|שפה רגולרית]])
#
# <math>\}</math> מספר האפסים בקלט שווה למספר האחדים <math>L=\{ x\in\{0,1\}^* \mid</math>. (זו שפה לא-רגולרית)
}}
נוכל כמובן להגדיר את מחלקת השפות הכריעות.
{{הגדרה|שם=מחלקת השפות הכריעות (או הרקורסיביות)|תוכן=
נגדיר את המחלקה <math>R</math> כקבוצת השפות ה'''כריעות''' (לחלופין, '''ניתנות להכרעה''' או '''רקורסיביות''', '''R'''ecursive)
<center>
<math>
</center>
}}
===כריעות למחצה חיובית===
גם אם שפה איננה כריעה לחלוטין, עדיין אפשר לחשוב על כריעות חלקית במובן כלשהו. אינטואיטיבית, שפה היא '''כריעה למחצה חיובית''' אם יש מכונת טיורינג העוצרת בוודאות על כל קלט השייך לשפה ומקבלת אותה, ואיננה עוצרת ומקבלת קלט שאינו שייך לשפה (יחד עם זאת, אם הקלט אינו שייך לשפה, היא איננה חייבת לעצור).
{{הגדרה|תוכן=
נאמר שמ"ט <math>M</math> '''מכריעה למחצה חיובית''' או '''מונה רקורסיבית''' שפה <math>L</math> אם היא <u>מקבלת</u> כל מילה ב־<math>L</math> ואיננה מקבלת מילה שאיננה ב-<math>L</math>
שפה <math>L</math> '''ניתנת למנייה רקורסיבית''' אם קיימת מ"ט <math>M</math> שמכריעה אותה למחצה חיובית. שפה <math>L</math> '''אינה נתנת למניה רקורסיבית''' אם לא קיימת מ״ט המקבלת אותה למחצה חיובית.
}}
{{חלון מידע|
מעט [[w:אטימולוגיה|אטימולוגיה]].
שפה נקראת "נתנת למניה רקורסיבית" מהסיבה הבאה. נניח ש-<math>L</math> היא שפה נתנת למניה רקורסיבית ע"י מ"ט <math>M</math>. נקח מניה כלשהי של המחרוזות על פני <math>\Sigma^*</math>. כעת נפעיל את <math>M</math> צעד אחד על המחרוזת הראשונה במניה, 2 צעדים על כ"א מ2 המחרוזות הראשונות במניה, 3 צעדים על כ"א מ3 -המחרוזות הראשונות במניה, וכו'. ברור שכל מחרוזת השייכת לL, תזוהה ככזו בשלב כלשהו ע"י כך שM תעצור ותקבל אותה. בכל פעם שמילה מתקבלת, נרשום אותה ברשימה בצד.
מצאנו דרך לבצע מניה של כל המחרוזות של <math>L</math>.
}}
להלן מספר דוגמאות לשפות נתנות למניה רקורסיבית:
{{דוגמה|שם=השפה האוניברסלית|תוכן=
'''השפה האוניברסלית''' מוגדרת כך: <math>L_U = \{ (\langle M \rangle,x) \mid x \in L(M) \}</math>{{ש}}
כל מילה בשפה זו מורכבת משתי מחרוזות – הראשונה היא קידוד של מכונה <math>M</math> והשניה הינה מחרוזת כלשהי <math>x</math>. המילה <math>(\langle M \rangle,x)</math> שייכת לשפה האוניברסלית אם המחרוזת <math>x</math> מתקבלת ע״י המכונה <math>M</math>.
נוכיח כריעות למחצה חיובית: נבנה מכונה אשר על הקלט <math>(\langle M \rangle,x)</math> [[תורת החישוביות/מכונת טיורינג אוניברסלית#המכונה האוניברסלית|מסמלצת הרצה]] של המכונה <math>M</math> על הקלט <math>x</math>, ומתנהגת כמותה (כלומר, אם <math>M</math> עצרה במצב <math>q_{acc}</math>, נקבל ואם עצרה ב־<math>q_{rej}</math> – נדחה. אם <math>M</math> אינה עוצרת, כך גם המכונה שבנינו.
}}
{{דוגמה|שם=שפת האלכסון|תוכן=
'''שפת האלכסון''' מוגדרת כך: <math>L_D = \{ \langle M \rangle \mid \langle M \rangle\in L(M)</math>{{ש}}
דהיינו, קידודי כל המכונות המקבלות את הקידוד של עצמן.
הקידוד של המכונה M ששפתה <math>L(M)=\Sigma^*</math> שייך ל־<math>L_D</math>, כי <math>M</math> מקבלת כל קלט ובפרט את המחרוזת <math>\langle M \rangle</math>.
נוכיח כריעות למחצה חיובית: כמקודם, נבנה מכונה שמסמלצת את הרצת <math>M</math> על הקלט <math>\langle M \rangle</math>, ומקבלת/דוחה בהתאם לסימולציית ההרצה.
}}
{{דוגמה|שם=שפת בעיית העצירה|תוכן=
שפת '''בעיית העצירה''' מוגדרת כך: <math>M \}</math> עוצרת על <math>L_{HP} = \{ (\langle M \rangle,x) \mid x</math>{{ש}}
נוכיח כריעות למחצה חיובית: נריץ את <math>M</math> על <math>x</math> – אם המכונה תעצור, נקבל. אחרת – <math>M</math> לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.
}}
גם כאן נוכל כמובן להגדיר את מחלקת השפות הנתנות למנייה רקורסיבית.
{{הגדרה|שם=מחלקת השפות הכריעות למחצה חיובית (או הנתנות למניה רקורסיביות)|תוכן=
נגדיר את המחלקה <math>RE</math> כקבוצת השפות ה'''כריעות למצה חיובית''' (לחלופין, '''נתנות למניה רקורסיבית''', '''R'''ecursively '''E'''numerable)
<center>
<math>RE= \{ L \;|\; L \text{ recursively enumerable} \}</math>
</center>
}}
===כריעות למחצה שלילית===
הגדרה זו מזכירה ל[[#כריעות למחצה חיובית|כריעות למחצה חיובית]] אך הפוכה לה. אינטואיטיבית, שפה היא '''כריעה למחצה שלילית''' אם יש מכונת טיורינג העוצרת בוודאות על כל קלט שאינו שייך לשפה ודוחה אותה, ואיננה עוצרת ודוחה קלט ששייך לשפה (יחד עם זאת, אם הקלט שייך לשפה, היא איננה חייבת לעצור).
{{הגדרה|תוכן=
נאמר שמ"ט <math>M</math> '''מכריעה למחצה שלילית''' היא <u>דוחה</u> כל מילה שאיננה ב־<math>L</math> ואיננה דוחה מילה ב-<math>L</math>
}}
{{הגדרה|שם=מחלקת השפות הכריעות למחצה שלילית)|תוכן=
נגדיר את המחלקה <math>coRE</math> כקבוצת השפות ה'''כריעות למצה שלילית''' ('''coR'''ecursively '''E'''numerable)
<center>
<math>RE= \{ L \;|\; L \text{ co-recusively enumerable} \}</math>
</center>
}}
==תכונות מחלקות הכריעות==
בחלק זה נוכיח תכונות של מחלקות הכריעות, ובפרט נוכיח שהתרשים הבא מתאר אותן.
[[File:RecursiveSets.png|500px|left|הייחסים בין קבוצות השפות]]
{{טענה|
שורה 45 ⟵ 120:
#<math>R=RE \cap coRE</math>}}
{{הוכחה
קל לראות כי <math>R \subseteq RE\cap coRE</math> כי אם השפה ניתנת להכרעה, אז ברור שקיימת מכונה שרק דוחה או רק מקבלת.
שורה 51 ⟵ 126:
מכיוון ש־<math>L\in RE</math> קיימת מ"ט <math>M_1</math> שמקבלת כל מילה <math>x\in L</math> ולא מקבלת <math>x\in \overline L</math>. באופן דומה, מכיוון ש־<math>L\in coRE</math> קיימת מ"ט <math>M_2</math> שדוחה כל מילה <math>x\in \overline L</math> ולא דוחה אף <math>x\in L</math>.{{ש}}
נריץ את שתי המכונות במקביל (למשל ע״י שני סרטים): אם <math>M_1</math> מקבלת, נקבל; ואם <math>M_2</math> דוחה, נדחה (הראשון מביניהם). כל מילה <math>x</math> או שייכת או לא שייכת ל־<math>L</math> ולכן בהכרח אחד משני המקרים לעיל ייתרחש לאחר זמן סופי (כלומר, אם הקלט בשפה הוא בהכרח ייתקבל ע״י <math>M_1</math> לאחר זמן סופי, ואם הוא לא בשפה הוא יידחה ע״י <math>M_2</math> לאחר זמן סופי). לפיכך, המכונה שבנינו עוצרת על כל קלט אפשרי עם התשובה הנכונה.
}}
{{טענה|תוכן=
:3.{{רווח קשיח|2}}<math>\ R</math> סגורה למשלים: אם <math>L \in R</math> אז גם השפה המשלימה, <math>\overline{L}\in R</math>{{רווח קשיח|2}}
}}
{{הוכחה|תוכן=
אם <math>L\in R</math> אז קיימת מ"ט M המכריעה את L. נבנה מ"ט <math>\overline M</math> ע״י החלפת המצבים הסופיים: <math>q_{acc,M}=q_{rej,\overline M}</math> ו־<math>q_{rej,M}=q_{acc,\overline M}</math>.{{ש}}
<math>\overline M</math> עוצרת על כל קלט (כי <math>M</math> עוצרת על כל קלט), ובנוסף, <math>\overline M</math> עונה הפוך מ־<math>M</math>, כלומר <math>L(\overline M)= \overline M</math> כנדרש.
}}
{{טענה|תוכן=
שורה 74 ⟵ 152:
:6.{{רווח קשיח|2}}<math>R, RE, coRE</math> סגורות לחיתוך ושרשור{{רווח קשיח|2}}}}
(תרגיל: הוכח).
[[קטגוריה:תורת החישוביות]]
| |||