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