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

נאמר שמ"ט <math>M</math> '''מכריעה למחצה חיובית''' או '''מונה רקורסיבית''' שפה <math>L</math> אם היא <u>מקבלת</u> כל מילה ב־<math>L</math> ואיננה מקבלת מילה שאיננה ב-<math>L</math>

שפה <math>L</math> ניתנת להכרעה למחצה חיובית (נקרא גם '''ניתנת למנייה רקורסיבית''') אם קיימת מ"ט <math>M</math> שמכריעה אותה למחצה חיובית. שפה <math>L</math> '''אינה נתנתניתנת למניה רקורסיבית''' אם לא קיימת מ״ט המקבלת אותה למחצה חיובית.{{ש}}{{ש}}