תורת החישוביות/כריעות שפות: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←כריעות למחצה שלילית: איחוד הגדרות |
←כריעות למחצה חיובית: איחוש הגדרות |
||
שורה 44:
נאמר שמ"ט <math>M</math> '''מכריעה למחצה חיובית''' או '''מונה רקורסיבית''' שפה <math>L</math> אם היא <u>מקבלת</u> כל מילה ב־<math>L</math> ואיננה מקבלת מילה שאיננה ב-<math>L</math>
שפה <math>L</math> '''ניתנת למנייה רקורסיבית''' אם קיימת מ"ט <math>M</math> שמכריעה אותה למחצה חיובית. שפה <math>L</math> '''אינה נתנת למניה רקורסיבית''' אם לא קיימת מ״ט המקבלת אותה למחצה חיובית.{{ש}}{{ש}}
אוסף כלל השפות הניתנות להכרעה למחצה חיובית יסומן <math>RE</math>
(לחלופין, אוסף כלל השפות ה'''ניתנות למניה רקורסיבית''', '''R'''ecursively '''E'''numerable):
<center>▼
<center><math>\ \}</math> קיימת מ"ט M ש<u>מקבלת</u> את כל המילים ב־L ו<u>אינה מקבלת</u> אף מילה שאינה ב־L (אבל לאו דווקא דוחה) <math>RE = \{ L \mid</math></center>
</center>{{ש}}▼
}}
שורה 77 ⟵ 82:
נוכיח כריעות למחצה חיובית: נריץ את <math>M</math> על <math>x</math> – אם המכונה תעצור, נקבל. אחרת – <math>M</math> לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.
▲<center>
▲</center>
}}
|