תורת החישוביות/מודל לבעיות הכרעה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מאין תקציר עריכה |
מ ←שקילות למודל הכללי: הגהה |
||
שורה 30:
:'''כיוון א'''': נניח שקיימת המכונה <math>M</math>, ובעזרתה נבנה את המכונה <math>M'</math>.
:בהנתן הקלט <math>(x, y)</math>, המכונה <math>M'</math> תריץ את <math>M</math> על x. אם <math>M</math> עוצרת עם תוצאה z, המכונה <math>M'</math> תבדוק האם <math>y = z</math>, ותקבל אם שווים (ואחרת, תדחה). נשים לב שאם <math>M</math> אינה עוצרת על x, אז <math>M'</math> לא תעצור גם כן.
:'''כיוון ב'''': נניח שקיימת המכונה <math>M'</math>, ובעזרתה נבנה את המכונה <math>M</math>.
:הרעיון הוא ש־<math>M</math> תסרוק את כל האפשרויות ל־<math>f(x)</math>, ועבור כל אפשרות y "תשאל" את <math>M'</math> האם <math>(x,y) \in L_f</math>, אם כן, אזי <math>y=f(x)</math> והמכונה תסיים. הבעיה היא שייתכנו ערכים של y עבורם <math>M'</math> לא עוצרת על <math>(x,y)</math>. כדי להתגבר על בעיה זו נבצע למעשה חקירה של כל ערכי ה־y "בו זמנית". המכונה תעבוד בעזרת מספר לולאות מקוננות (כל אחת יכולה להשתמש בסרט אחד או יותר, לפי מה ש[[תורת_החישוביות/מכונת_טיורינג_אוניברסלית#שקילות מ"ט מרובת סרטים|כבר ראינו]]). נניח שהקלט הוא x. :#בלולאה החיצונית ביותר, המכונה תעדכן מונה מספרי רץ <math>n = 0, 1, 2,\ldots</math>
:#עבור כל n, בלולאה פנימית יותר, המכונה תייצר את סדרת המחרוזות שאורכן לכל היותר <math>n</math>, כלומר <math>\{y | y \in \Sigma^*, |y| \leq n\}</math>.
| |||