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

עד כה עסקנו במכונות טיורינג כלליות, המסוגלות לחשב פונקציה $f:{\mathrm{\Sigma }}^{*}\to {\mathrm{\Sigma }}^{*}$. בהמשך הקורס נתמקד בקבוצה קטנה מתוך כלל מכונות הטיורינג, אשר מבצעות הכרעה של שפה, כלומר, מכונות המחשבות פונקציות בעלות פלט בינארי: כן או לא $f:{\mathrm{\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)\ne \text{accept}\}$, ולכן $L_{\text{not accept}}(M)=L_{\text{reject}}(M)\cup \{x\mid M\text{ does not halt on }x\}$.

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

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

קיימת מכונה $M$ המחשבת את $f$תבנית:רווח קשיח אם״םתבנית:רווח קשיח קיימת מכונה $M^{\prime }$ המקבלת את $L_f$

תבנית:תורת החישוביות