תורת החישוביות/מודל לבעיות הכרעה

עד כה עסקנו במכונות טיורינג כלליות, המסוגלות לחשב פונקציה $f:\Sigma ^{*}\to \Sigma ^{*}$. בהמשך הקורס נתמקד בקבוצה קטנה מתוך כלל מכונות הטיורינג, אשר מבצעות הכרעה של שפה, כלומר, מכונות המחשבות פונקציות בעלות פלט בינארי: כן או לא $f:\Sigma ^{*}\to \{0,1\}$. מודל זה בעל חשיבות רבה, ולמעשה הוא שקול למודל הכללי ביותר.

לשם פשטות המודל, על מנת לסמן "קבלה" או "דחייה" נגדיר מצבים סופיים מתאימים $q_{acc},q_{rej}\in F$. כלומר, על מנת לקבל את הקלט, המכונה צריכה לעבור למצב הסופי $q_{acc}$ ועל מנת לדחותו, על המכונה לעבור למצב $q_{rej}$, ואין חשיבות לתוכן הסרט בעת מעבר למצב הסופי (כלומר, אינה צריכה לכתוב "0" או "1", המעבר למצב המתאים מספיק). כמו כן, ניתן להניח ש-$q_{acc},q_{rej}$ הם המצבים הסופיים היחידים, כי מצבים נוספים (למשל $q_{acc1},q_{acc2},...$) ניתנים להחלפה באחד משני המצבים לעיל, בהתאם לשאלה האם הם גורמים לקבלה או דחיה.

השפה המתקבלת והנדחית על-ידי מכונה

מכיוון שעל כל קלט, מכונה $M$ יכולה לענות כן או לא (קבלה או דחיה), היא למעשה מחלקת את מרחב הקלט לשתי קבוצות: קבוצת המילים שעליהן היא עונה "כן" וקבוצת שאר המילים, עליהן היא עונה "לא" או לא עוצרת. נסמן ב-$L(M)$ את קבוצת המילים שהמכונה עונה עליהן "כן", ונקרא לקבוצה זו השפה המתקבלת על-ידי המכונה M:

$L(M)\triangleq L_{acc}=\{x\mid M(x)={\text{ accept}}\}$

באופן דומה, ניתן להגדיר את השפה הנדחית על ידי המכונה $L_{rej}(M)\triangleq \{x\mid M(x)={\text{ reject}}\}$.

נדגיש כי לכל קלט ייתכנו שלושה מצבים: המכונה עצרה וקיבלה את הקלט, המכונה עצרה ודחתה את הקלט או המכונה לא עצרה. קלט ש"לא התקבל" על-ידי מכונה הוא קלט שנדחה או שהמכונה לא עצרה בעת החישוב, כלומר ${\overline {L(M)}}=L_{\text{not accept}}\triangleq \{x\mid M(x)\neq {\text{accept}}\}$, ולכן $L_{\text{not accept}}(M)=L_{\text{reject}}(M)\cup \{x\mid M{\text{ does not halt on }}x\}$.

להרחבה בנושא שפות פורמליות, וסימונים מקובלים, ראה אוטומטים ושפות פורמליות/שפות פורמליות.

שקילות למודל הכללי

כפי שנאמר לעיל, המודל של הכרעת שפות שקול למודל הכללי. נניח פונקציה (חלקית או מלאה) מסויימת $f:S\to \Sigma ^{*}$, על התחום $S\subseteq \Sigma ^{*}$. נגדיר שפה $L_{f}=\{(x,f(x))\mid x\in S\}$. נראה ששני המודלים הנ״ל שקולים, דהיינו נוכיח את המשפט הבא:

קיימת מכונה $M$ המחשבת את $f$     אם״ם     קיימת מכונה $M'$ המקבלת את $L_{f}$

הוכחה:

כיוון א': נניח שקיימת המכונה $M$, ובעזרתה נבנה את המכונה $M'$.

בהנתן הקלט $(x,y)$, המכונה $M'$ תריץ את $M$ על x. אם $M$ עוצרת עם תוצאה z, המכונה $M'$ תבדוק האם $y=z$, ותקבל אם שווים (ואחרת, תדחה). נשים לב שאם $M$ אינה עוצרת על x, אז $M'$ לא תעצור גם כן.

כיוון ב': נניח שקיימת המכונה $M'$, ובעזרתה נבנה את המכונה $M$.

הרעיון הוא ש־$M$ תסרוק את כל האפשרויות ל־$f(x)$, ועבור כל אפשרות y "תשאל" את $M'$ האם $(x,y)\in L_{f}$, אם כן, אזי $y=f(x)$ והמכונה תסיים. הבעיה היא שייתכנו ערכים של y עבורם $M'$ לא עוצרת על $(x,y)$. כדי להתגבר על בעיה זו נבצע למעשה חקירה של כל ערכי ה־y "בו זמנית". המכונה תעבוד בעזרת מספר לולאות מקוננות (כל אחת יכולה להשתמש בסרט אחד או יותר, לפי מה שכבר ראינו). נניח שהקלט הוא x.

1. בלולאה החיצונית ביותר, המכונה תעדכן מונה מספרי רץ $n=0,1,2,\ldots$
2. עבור כל n, בלולאה פנימית יותר, המכונה תייצר את סדרת המחרוזות שאורכן לכל היותר $n$, כלומר $\{y|y\in \Sigma ^{*},|y|\leq n\}$.
3. עבור כל $n$ ומחרוזת $y$, בלולאה פנימית יותר, המכונה תריץ $n$ צעדים של $M'$ על $(x,y)$. אם בשלב כלשהו של הלולאה הפנימית ביותר $M'$ תעצור על $(x,y)$ בתשובה חיובית, אז המכונה $M$ תחזיר את $y$ כפלט.

שיטה זו של "מיקבול וירטואלי" של חישובים שונים ע"י סדרה עולה של חישובים חלקיים נקראת dovetailing, והיא טכניקה שימושית בחישוביות.

הפרק הקודם: מכונת טיורינג אוניברסלית

מודל לבעיות הכרעה

הפרק הבא: כריעות שפות