ברוכים הבאים ליחידת הלימוד "שפות כריעות וניתנות לזיהוי" בקורס "מודלים חישוביים" (20604). יחידה זו היא אבן יסוד בהבנת גבולות החישוב. נחקור את ההבחנה הקריטית בין בעיות שניתן לפתור באופן מלא ואלגוריתמי (כלומר, תמיד נקבל תשובה נכונה בזמן סופי), לבין בעיות שניתן רק "לזהות" (כלומר, אם התשובה חיובית, נדע זאת בסופו של דבר, אך אם היא שלילית, ייתכן שלעולם לא נגיע למסקנה). הבנה מעמיקה של מושגים אלו חיונית לא רק למבחן, אלא גם להבנת מהות מדעי המחשב.
מכונות טיורינג כמודל חישובי
בליבת תורת החישוביות עומד מודל מכונת טיורינג (TM), המשמש כהגדרה פורמלית למושג "אלגוריתם" או "חישוב". כל מה שניתן לחשב על ידי מחשב מודרני, ניתן לחשב על ידי מכונת טיורינג, ולהיפך (טענת צ'רץ'-טיורינג).
פעולות מכונת טיורינג:
- קריאה: קוראת תו מהתא הנוכחי בסרט.
- כתיבה: כותבת תו לתא הנוכחי בסרט.
- הזזה: מזיזה את הראש שמאלה או ימינה.
- שינוי מצב: עוברת למצב פנימי חדש.
- עצירה (Halt): המכונה מפסיקה את פעולתה. היא יכולה לעצור במצב מקבל (accept) או במצב דוחה (reject).
הגדרת שפות כריעות וניתנות לזיהוי
היכולת של מכונת טיורינג לעצור היא המפתח להבחנה בין סוגי הבעיות השונים. שפה היא אוסף של מילים (קלט), ומכונת טיורינג "מכריעה" או "מזהה" שפה בהתאם להתנהגותה עבור מילים בשפה ומחוץ לה.
- אם w שייך ל-L, אז M עוצרת במצב מקבל.
- אם w אינו שייך ל-L, אז M עוצרת במצב דוחה.
- אם w שייך ל-L, אז M עוצרת במצב מקבל.
- אם w אינו שייך ל-L, אז M עשויה לעצור במצב דוחה, או שהיא עשויה לרוץ לנצח (לא לעצור).
ההבחנה המכרעת: כריעות מול זיהוי
ההבדל המהותי בין שפה כריעה לשפה ניתנת לזיהוי טמון בהתנהגות מכונת הטיורינג עבור קלטים שאינם בשפה.
שפה כריעה
קיימת מכונת טיורינג שתמיד עוצרת (Halt) עבור כל קלט. אם הקלט בשפה, היא מקבלת. אם הקלט אינו בשפה, היא דוחה. יש לנו תמיד תשובה סופית וחד-משמעית.
שפה ניתנת לזיהוי
קיימת מכונת טיורינג שמקבלת קלטים בשפה (ועוצרת). אך עבור קלטים שאינם בשפה, היא עשויה לדחות (ולעצור) או לרוץ לנצח (ולא לעצור). אין לנו ערובה לתשובה סופית עבור קלטים שאינם בשפה.
דוגמאות קלאסיות:
- שפה כריעה: שפת כל הגרפים הקשירים. ניתן לבנות אלגוריתם (TM) שתמיד יקבע אם גרף נתון קשיר או לא.
- שפה ניתנת לזיהוי (אך לא כריעה): בעיית העצירה (HALTTM). זוהי שפת כל זוגות <M, w> כך שמכונת טיורינג M עוצרת על קלט w. ניתן לבנות TM שמזהה אותה (פשוט מריצים את M על w, ואם היא עוצרת, מקבלים). אך הוכח שאין TM שמכריעה אותה – כלומר, אין אלגוריתם שתמיד יקבע אם M עוצרת על w או לא.
הקשר בין שפות כריעות, ניתנות לזיהוי וניתנות לזיהוי-למפרע
הקשר המרכזי הוא:
- שפה L היא כריעה אם ורק אם L ניתנת לזיהוי וגם L ניתנת לזיהוי-למפרע.
משמעות הדבר היא שאם אנו יכולים לבנות מכונת טיורינג שמזהה את השפה (מקבלת קלטים חוקיים) וגם מכונת טיורינג שמזהה את המשלים שלה (מקבלת קלטים לא חוקיים), אזי ניתן "להריץ" את שתי המכונות במקביל (למשל, על ידי ריצה לסירוגין צעד אחר צעד). אחת מהן בוודאות תעצור ותקבל, ובכך נדע אם הקלט בשפה או לא, ותמיד נקבל תשובה סופית.
שאלות לדיון
- הסבירו מדוע בעיית העצירה (HALTTM) היא שפה ניתנת לזיהוי אך אינה כריעה.
- תארו את ההבדל המהותי בהתנהגות מכונת טיורינג המכריעה שפה לעומת מכונה המזהה שפה, בהקשר של קלטים שאינם בשפה.
- האם כל שפה סופית היא כריעה? נמקו.
- האם שפת כל מכונות הטיורינג שמקבלות את המילה הריקה (ε) היא כריעה, ניתנת לזיהוי, או לא ניתנת לזיהוי?
נקודות לתשובת מודל
- לגבי בעיית העצירה: ניתן לבנות TM שמריצה את M על w. אם M עוצרת, ה-TM המזהה מקבלת. אם M לא עוצרת, ה-TM המזהה גם לא עוצרת. לכן היא ניתנת לזיהוי. היא אינה כריעה כי הוכח שאין אלגוריתם שפותר את בעיית העצירה לכל המקרים.
- לגבי ההבדל בהתנהגות: מכונה מכריעה תמיד עוצרת ודוחה קלטים שאינם בשפה. מכונה מזהה עשויה לרוץ לנצח עבור קלטים שאינם בשפה, ולכן אין ערובה לתשובה שלילית.
- לגבי שפה סופית: כן, כל שפה סופית היא כריעה. ניתן לבנות מכונת טיורינג שמכילה רשימה סופית של כל המילים בשפה, ובודקת האם הקלט נמצא ברשימה. בדיקה זו תמיד תסתיים בזמן סופי.
- לגבי שפת מכונות הטיורינג שמקבלות ε: זוהי שפה ניתנת לזיהוי אך לא כריעה. ניתן לזהות אותה על ידי הרצת M על ε. אם M מקבלת, אז ה-TM המזהה מקבלת. אם M לא מקבלת (דוחה או לא עוצרת), ה-TM המזהה לא תדע זאת בוודאות. הוכח שהיא אינה כריעה (לרוב על ידי רדוקציה מבעיית העצירה).