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