תורת החישוביות/מודל לבעיות הכרעה: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←שקילות למודל הכללי: תקלדה |
|||
שורה 23:
===שקילות למודל הכללי ===
כפי שנאמר לעיל, המודל של הכרעת שפות שקול למודל הכללי. נניח פונקציה (חלקית או מלאה) מסויימת <math>f: S \to \Sigma^*</math>, על התחום <math>S\
נראה ששני המודלים הנ״ל שקולים, דהיינו נוכיח את המשפט הבא:
:'''קיימת מכונה <math>M</math> המחשבת את <math>f</math>{{רווח קשיח|4}} אם״ם{{רווח קשיח|4}} קיימת מכונה <math>M'</math> <u>המקבלת</u> את <math>L_f</math>'''
נניח שקיימת המכונה M, ובעזרתה נבנה את המכונה ▼
#בלולאה החיצונית ביותר, המכונה תעדכן מונה מספרי רץ <math>n = 0, 1, 2,\ldots</math>▼
#עבור כל n, בלולה פנימית יותר, המכונה תייצר את סדרת המחרוזות שאורכן לכל היותר n, כלומר <math>\{y | y \in \Sigma^*, |y| \leq n\}</math>.▼
{{הוכחה|
▲:'''כיוון א'''': נניח שקיימת המכונה <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</math>, בלולאה פנימית יותר, המכונה תריץ <math>n</math> צעדים של <math>M'</math> על <math>(x, y)</math>. אם בשלב כלשהו של הלולאה הפנימית ביותר <math>M'</math> תעצור על <math>(x, y)</math> בתשובה חיובית, אז המכונה <math>M</math> תחזיר את <math>y</math> כפלט.}}
{{חלון מידע|שיטה זו של "מיקבול וירטואלי" של חישובים שונים ע"י סדרה עולה של חישובים חלקיים נקראת [[w:en:Dovetailing_(computer_science)|dovetailing]], והיא טכניקה שימושית בחישוביות.}}
| |||