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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
דוגמאות
שורה 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>.
 
[[קטגוריה:תורת החישוביות]]