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

נניח ש-<math>L</math> היא שפה כריעה למחצה חיובית ע״י מ״ט <math>M</math>. כעת נבצע הרצה מבוקרת של M על כלל המחרוזות האפשריות, כלומר, נפעיל את <math>M</math> צעד אחד על המחרוזת הראשונה ב־<math>\Sigma^*</math> (נניח, לפי סדר לקסיקוגרפי), אח״כ 2 צעדים על כ״א מ־2 המחרוזות הראשונות במניה, אח״כ 3 צעדים על כ״א מ־3 המחרוזות הראשונות וכו'. אם M מקבלת מילה כלשהי, E רושמת את המילה על הסרט וממשיכה הלאה. ברור שכל מחרוזת השייכת ל־L, תזוהה ככזו בשלב כלשהו ע"י כך ש־M תעצור ותקבל אותה. ולכן E רושמת כל מילה אפשרית ב־L לאחר זמן סופי.

 

}}