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

נבנה מכונה M שמריצה את <math>M_1</math> ולאחר מכן את <math>M_2</math> (למשל, על סרט שני אליו מועתק הקלט בהתחלה). החזר "כן" אם אחת המכונות קיבלה, ואחרת -– החזר "לא". נשים לב ששתי המכונות עוצרות על כל קלט ולכן גם M תעצור על כל קלט.

ההוכחה לעיל אינה מספיק טוב, מכיוון שייתכן ש־<math>M_1</math> אינה עוצרת, ולכן לעולם לא נגיע לשלב בו אנחנו מריצים את <math>M_2</math>. במילים אחרות, אסור לנו להריץ את שתי המכונות בטור, וצריך להריץ אותן בצורה מקבילה, כל אחת על סרט אחר. מסמלצים צעד מ־<math>M_1</math> ולאחריו צעד של <math>M_2</math> וחוזר חלילה. אם אחת המכונות קיבלה – עוצרים ומקבלים. אם שתיהן בלולאה אינסופית, גם המכונה שבנינו לא תעצור (אך זה מותר עבור קלט שאינו בשפה, לפי הגדרת המחלקה <math>\ RE</math>).