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

בהנתן הקלט
<math>(x, y)</math>, המכונה <math>M'</math> תריץ את M על x. אם M עוצרת עם תוצאה z, המכונה

, ובעזרתה נבנה את המכונה M. המכונה תעבוד בעזרת מספר לולאות מקוננות (כל אחת יכולה להשתמש בסרט אחד או יותר, לפי מה ש[[תורת_החישוביות/מכונת_טיורינג_אוניברסלית#שקילות מ"ט מרובת סרטים|כבר ראינו]]). נניח שהקלט הוא x.

#עבור כל n, בלולה פנימית יותר, המכונה תייצר את סדרת המחרוזות שאורכן לכל היותר n, כלומר <math>\{zy | zy \in \Sigma^*, |zy| \leq n\}</math>.

# עבור כל n ומחרוזת y, בלולאה פנימית יותר, המכונה תריץ n צעדים של <math>M'</math> על <math>(x, zy)</math>.

תעצור על <math>(x, zy)</math> בתשובה חיובית, אז המכונה M תחזיר את zy כתשובה שלה לקלט x.