תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←כריעות: מחלקות של שפות: הרחבה |
דוגמאות |
||
שורה 57:
(תרגיל: הוכח).
== דוגמאות לשפות==
נביא מספר דוגמאות לשפות ב־RE. בפרק [[תורת החישוביות/כריעות שפות/שפות שאינן כריעות|שפות שאינן כריעות]] נוכיח כי השפות להלן '''אינן כריעות'''
1. '''השפה האוניברסלית''', <math>L_U = \{ (\langle M \rangle,x) \mid x \in L(M) \}</math>{{ש}}
כל מילה בשפה זו מורכבת משתי מחרוזות – הראשונה היא קידוד של מכונה M והשניה הינה מחרוזת כלשהי x. המילה <math>(\langle M \rangle,x)</math> שייכת לשפה האוניברסלית אם המחרוזת x מתקבלת ע״י המכונה M.
:שייכות ל־RE: נבנה מכונה אשר על הקלט <math>(\langle M \rangle,x)</math> [[../מכונת טיורינג אוניברסלית#המכונה האוניברסלית|מסמלצת הרצה]] של המכונה M על הקלט x, ומתנהגת כמותה (כלומר, אם M עצרה במצב <math>q_{acc}</math>, נקבל ואם עצרה ב־<math>q_{rej}</math> – נדחה. אם M אינה עוצרת, כך גם המכונה שבנינו.
2. '''שפת האלכסון''', <math>L_D = \{ \langle M \rangle \mid \langle M \rangle\in L(M)</math>{{ש}}
אוסף כל המחרוזות, שהמכונה שהן מקודדות מקבלת את מחרוזת הקלט (שהיא הקידוד עצמו של המכונה). כלומר - קידודי כל המכונות המקבלות את הקידוד של עצמן. דוגמא, הקידוד של המכונה M ששפתה <math>L(M)=\Sigma^*</math> שייך ל־<math>L_D</math>, כי M מקבלת כל קלט ובפרט את המחרוזת <math>\langle M \rangle</math>.
:שייכות ל־RE: כמקודם, נבנה מכונה שמסמלצת את הרצת M על הקלט <math>\langle M \rangle</math>, ומקבלת/דוחה בהתאם לסימולציית ההרצה.
3. '''בעיית העצירה''', <math>M \}</math> עוצרת על <math>\text{HP} = \{ (\langle M \rangle,x) \mid x</math>{{ש}}
:שייכות ל־RE: נריץ את M על x – אם המכונה תעצור, נקבל. אחרת – M לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.
מההגדרה, נובע עבור השפות המשלימות, <math>\overline{L_U}, \overline{L_D}, \overline{\text{HP}} \in coRE</math>.
[[קטגוריה:תורת החישוביות]]
|