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

תוכן שנמחק תוכן שנוסף
Gran (שיחה | תרומות)
Gran (שיחה | תרומות)
שורה 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> לא עצרה וגם המכונה המסמלצת בלולאה אינסופית, ואינה מקבלת את הקלט הנ״ל.
}}
 
גם כאן נוכל כמובן להגדיר את מחלקת השפות הנתנות למנייה רקורסיבית.
{{הגדרה|שם=מחלקת השפות הכריעות למחצה חיובית (או הנתנות למניה רקורסיביות)|תוכן=
 
נגדיר את המחלקה <math>RE</math> כקבוצת השפות ה'''כריעות למצה חיובית''' (לחלופין, '''נתנות למניה רקורסיבית''', '''R'''ecursively '''E'''numerable)
<center>
<math>RE= \{ L \;|\; L \text{ recursively enumerable} \}</math>
</center>
}}