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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 63:
}}
 
====דוגמאות====
 
להלן מספר דוגמאות לשפות נתנות למניה רקורסיבית:
 
{{דוגמה|שם=1. '''השפה האוניברסלית|תוכן''' מוגדרת כך: <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>L_U = \{ (\langle M \rangle,x) \mid x \in L(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>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>{{ש}}
דהיינו, קידודי כל המכונות המקבלות את הקידוד של עצמן.
 
2. '''השפהשפת האוניברסליתהאלכסון''' מוגדרת כך: <math>L_UL_D = \{ (\langle M \rangle,x) \mid x\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>, ומקבלת/דוחה בהתאם לסימולציית ההרצה.
:הקידוד של המכונה 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>{{ש}}
 
3. שפת '''בעיית העצירה''' מוגדרת כך: <math>M \}</math> עוצרת על <math>L_{HP} = \{ (\langle M \rangle,x) \mid x</math>{{ש}}
:נוכיח כריעות למחצה חיובית: נריץ את <math>M</math> על <math>x</math> – אם המכונה תעצור, נקבל. אחרת – <math>M</math> לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.
}}
 
===כריעות למחצה שלילית===