הצגת המקור של הדף "תורת החישוביות/מודל לבעיות הכרעה"

{{תורת החישוביות}}

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

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

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

מכיוון שעל כל קלט, מכונה <math>M</math> יכולה לענות כן או לא (קבלה או דחיה), היא למעשה מחלקת את מרחב הקלט לשתי קבוצות: קבוצת המילים שעליהן היא עונה "כן" וקבוצת שאר המילים, עליהן היא עונה "לא" או לא עוצרת. נסמן ב-<math>L(M)</math> את קבוצת המילים שהמכונה עונה עליהן "כן", ונקרא לקבוצה זו '''השפה המתקבלת על-ידי המכונה M''': 
<center> <math>L(M) \triangleq L_{acc}= \{ x\mid M(x) = \text{ accept}\}</math></center>
באופן דומה, ניתן להגדיר את השפה ה'''נדחית''' על ידי המכונה 
<math>L_{rej}(M) \triangleq \{ x \mid M(x)=\text{ reject} \}</math>. 

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

{{-}}
{{חלון מידע|להרחבה בנושא שפות פורמליות, וסימונים מקובלים, ראה [[אוטומטים ושפות פורמליות/שפות פורמליות]].}}

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

כפי שנאמר לעיל, המודל של הכרעת שפות שקול למודל הכללי. נניח פונקציה (חלקית או מלאה) מסויימת <math>f: S \to \Sigma^*</math>, על התחום <math>S\subseteq \Sigma^*</math>. נגדיר שפה <math>L_f = \{ (x, f(x)) \mid x\in S\}</math>. 
נראה ששני המודלים הנ״ל שקולים, דהיינו נוכיח את המשפט הבא:
:'''קיימת מכונה <math>M</math> המחשבת את <math>f</math>{{רווח קשיח|4}} אם״ם{{רווח קשיח|4}} קיימת מכונה <math>M'</math> <u>המקבלת</u> את <math>L_f</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 | y \in \Sigma^*, |y| \leq n\}</math>.
:# עבור כל <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]], והיא טכניקה שימושית בחישוביות.}}


{{תורת החישוביות|מוגבל}}
[[קטגוריה:תורת החישוביות]]