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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
←‏כריעות למחצה חיובית: M מכריעה שונה מ M מונה רקורסיבית
Gran (שיחה | תרומות)
שורה 56:
מעט [[w:אטימולוגיה|אטימולוגיה]].
 
שפה כריעה למחצה חיובית נקראת גם "ניתנת למניה רקורסיבית" מכיוון שלכל שפה כנ"ל קיימת מ״ט E ש"מייצרת" את כל המילים ב־L, כלומר, היא רושמת על סרט הזיכרון עוד ועוד מילים מתוך L, ללא סדר מסויים, כך שכל מילה ב־L תופיע על הסרט אחרי זמן סופי. מכונה כזו נקראת "מונה רקורסיבית" משום שהיא מונה את המילים שב־L.
שפה נקראת "נתנת למניה רקורסיבית" מהסיבה הבאה. נניח ש-<math>L</math> היא שפה נתנת למניה רקורסיבית ע"י מ"ט <math>M</math>. נקח מניה כלשהי של המחרוזות על פני <math>\Sigma^*</math>. כעת נפעיל את <math>M</math> צעד אחד על המחרוזת הראשונה במניה, 2 צעדים על כ"א מ2 המחרוזות הראשונות במניה, 3 צעדים על כ"א מ3 -המחרוזות הראשונות במניה, וכו'. ברור שכל מחרוזת השייכת לL, תזוהה ככזו בשלב כלשהו ע"י כך שM תעצור ותקבל אותה. בכל פעם שמילה מתקבלת, נרשום אותה ברשימה בצד.
 
מצאנו דרך לבצע מניה של כל המחרוזות של <math>L</math>.
שפה נקראת "נתנת למניה רקורסיבית" מהסיבה הבאה. נניח ש-<math>L</math> היא שפה נתנתכריעה למניהלמחצה רקורסיביתחיובית ע"יע״י מ"טמ״ט <math>M</math>. נקחכעת מניהנבצע כלשהיהרצה מבוקרת של המחרוזותM על פניכלל <math>\Sigma^*</math>.המחרוזות האפשריות, כלומר, כעת נפעיל את <math>M</math> צעד אחד על המחרוזת הראשונה במניהב־<math>\Sigma^*</math> (נניח, לפי סדר לקסיקוגרפי), אח״כ 2 צעדים על כ"אכ״א מ2מ־2 המחרוזות הראשונות במניה, אח״כ 3 צעדים על כ"אכ״א מ3מ־3 -המחרוזות הראשונות במניה, וכו'. אם M מקבלת מילה כלשהי, E רושמת את המילה על הסרט וממשיכה הלאה. ברור שכל מחרוזת השייכת לLל־L, תזוהה ככזו בשלב כלשהו ע"י כך שMש־M תעצור ותקבל אותה. בכלולכן פעםE שמילהרושמת מתקבלת,כל נרשוםמילה אותהאפשרית ברשימהב־L בצדלאחר זמן סופי.
 
נשים לב שהסדר של המניה אינו ידוע. ב[[../תרגילים#שפה כריעה ניתנת למניה לקסיקוגרפית|תרגיל]] נראה שקיימת מ״ט E המונה את L '''לפי סדר לקיסקוגרפי''' אם״ם <math>L\in R</math>.
}}