מודלים חישוביים — מרחב למידה אישי

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

הקדמה לאי-כריעות ומושגי יסוד

בתורת החישוביות, אנו מבחינים בין סוגים שונים של בעיות בהתאם ליכולת של מכונת טיורינג לפתור אותן.

בעיה כריעה (Decidable Problem): בעיה שקיים עבורה אלגוריתם (מכונת טיורינג) שתמיד עוצרת ונותנת תשובה נכונה (כן/לא) עבור כל קלט אפשרי. שפות כריעות נקראות גם שפות רקורסיביות.

בעיה כריעה למחצה (Recognizable Problem / Semi-decidable Problem): בעיה שקיים עבורה אלגוריתם (מכונת טיורינג) שמקבל את כל הקלטים השייכים לשפה, אך עבור קלטים שאינם שייכים לשפה, האלגוריתם עשוי לדחות או להיכנס ללולאה אינסופית. שפות כריעות למחצה נקראות גם שפות ניתנות למנייה רקורסיבית (recursively enumerable).

בעיה בלתי-כריעה (Undecidable Problem): בעיה שאינה כריעה. כלומר, לא קיים עבורה אלגוריתם שתמיד עוצר ונותן תשובה נכונה לכל קלט. בעיה בלתי-כריעה יכולה להיות כריעה למחצה (אם קיים אלגוריתם שמקבל את המקרים החיוביים) או לא כריעה למחצה כלל.

הוכחת אי-כריעות של בעיה חדשה היא לרוב מורכבת ודורשת שימוש בטכניקת הרדוקציה.

רדוקציות: הכלי המרכזי להוכחת אי-כריעות

רדוקציה (צמצום) היא טכניקה המאפשרת לנו להראות קשר בין שתי בעיות. הרעיון המרכזי הוא שאם נוכל "לתרגם" מופע של בעיה אחת למופע של בעיה שנייה, כך שפתרון הבעיה השנייה ייתן לנו גם פתרון לבעיה הראשונה, אזי הבעיה הראשונה "קלה" או "לא קשה יותר" מהבעיה השנייה.

רדוקציית מיפוי (Mapping Reduction / Many-one Reduction): נאמר ששפה A ניתנת לרדוקציית מיפוי לשפה B, המסומן A ≤_m B, אם קיימת פונקציה ניתנת לחישוב f : Σ* → Σ* (פונקציה שניתן לחשב על ידי מכונת טיורינג שתמיד עוצרת) כך שלכל מילה w מתקיים: w ∈ A אם ורק אם f(w) ∈ B.

חשיבות הרדוקציות להוכחת אי-כריעות:

אם A ≤_m B ו-B כריעה, אז A כריעה. (אם יש לנו פותר ל-B, נוכל לבנות פותר ל-A על ידי חישוב f(w) ושימוש בפותר של B).
העיקר להוכחת אי-כריעות: אם A ≤_m B ו-A בלתי-כריעה, אז B בלתי-כריעה. (זוהי ההיפוך הלוגי של הטענה הקודמת. אם B הייתה כריעה, אז גם A הייתה כריעה, בסתירה להנחה).

בעיות יסוד בלתי-כריעות

כדי להוכיח שבעיה חדשה היא בלתי-כריעה, אנו זקוקים לנקודת התחלה – בעיה ידועה שאינה כריעה. בעיית העצירה (Halting Problem) היא הדוגמה הקלאסית, אך בעיית הקבלה (Acceptance Problem) היא לרוב נקודת המוצא הפורמלית ביותר, שאי-ככריעותה מוכחת באמצעות אלכסון.

בעיית הקבלה (A_TM)

הגדרה: A_TM = { <M, w> | M היא מכונת טיורינג ו-M מקבלת את w }.
סטטוס: בלתי-כריעה, אך כריעה למחצה. זוהי בעיית הבסיס שאי-כריעותה מוכחת לרוב באמצעות שיטת האלכסון.

בעיית העצירה (HALT_TM)

הגדרה: HALT_TM = { <M, w> | M היא מכונת טיורינג ו-M עוצרת על הקלט w }.
סטטוס: בלתי-כריעה, אך כריעה למחצה. ניתן להוכיח את אי-כריעותה באמצעות רדוקציה מ-A_TM.

בעיית הריקות (E_TM)

הגדרה: E_TM = { <M> | M היא מכונת טיורינג ו-L(M) = ∅ } (כלומר, השפה שמכונה M מקבלת היא ריקה).
סטטוס: בלתי-כריעה, ואינה כריעה למחצה. זוהי דוגמה לבעיה "קשה יותר" מ-A_TM.

בעיית השקילות (EQ_TM)

הגדרה: EQ_TM = { <M₁, M₂> | M₁ ו-M₂ הן מכונות טיורינג ו-L(M₁) = L(M₂) }.
סטטוס: בלתי-כריעה, ואינה כריעה למחצה. ניתן להוכיח את אי-כריעותה באמצעות רדוקציה מ-E_TM.

כיצד לבנות הוכחת אי-כריעות באמצעות רדוקציה (נושא בחינה קריטי):

הוכחת אי-כריעות באמצעות רדוקציה היא טכניקה מרכזית בבחינות. הנה השלבים הסטנדרטיים:

זיהוי בעיות: נניח שברצוננו להוכיח שבעיה L2 (הבעיה החדשה) היא בלתי-כריעה. נבחר בעיה L1 ידועה שהיא בלתי-כריעה (לרוב A_TM או HALT_TM).
הנחת בשלילה: נניח בשלילה ש-L2 כריעה. כלומר, קיים אלגוריתם (מכונת טיורינג) R שפותר את L2 (תמיד עוצר ונותן תשובה נכונה).
בניית אלגוריתם ל-L1: נבנה אלגוריתם חדש (מכונת טיורינג) D, שמשתמש ב-R כ"קופסה שחורה" (כפונקציית עזר), כדי לפתור את L1.
- האלגוריתם D יקבל קלט w' עבור L1.
- D יבצע טרנספורמציה (פונקציית רדוקציה f) על w' כדי ליצור קלט w'' המתאים ל-L2.
- D יפעיל את R על w''.
- D יחזיר את התשובה של R כפתרון ל-w' ב-L1.
הוכחת נכונות הרדוקציה: נוודא שפונקציית הטרנספורמציה f אכן מקיימת את התנאי: w' ∈ L1 אם ורק אם f(w') ∈ L2. זהו השלב הקריטי ביותר, שבו אנו מתארים כיצד לבנות את f (לרוב, f בונה מכונת טיורינג חדשה M' מתוך M ו-w המקוריים).
סתירה: מכיוון ש-D פותר את L1, ו-L1 ידועה כבלתי-כריעה, הגענו לסתירה. לכן, ההנחה המקורית ש-L2 כריעה שגויה, ו-L2 חייבת להיות בלתי-כריעה.

טיפ לבחינה: שימו לב היטב לכיוון הרדוקציה! תמיד מצמצמים מבעיה בלתי-כריעה ידועה (L1) לבעיה שרוצים להוכיח שהיא בלתי-כריעה (L2). כלומר, L1 ≤_m L2.

שאלות לדיון

מה ההבדל המהותי בין שפה כריעה למחצה לבין שפה שאינה כריעה למחצה? תן דוגמה לכל אחת.
מדוע בעיית הקבלה (A_TM) נחשבת לרוב לנקודת המוצא להוכחות אי-כריעות, ולא בעיית העצירה (HALT_TM)?
הוכח כי בעיית הריקות (E_TM) היא בלתי-כריעה, באמצעות רדוקציה מ-A_TM.
כיצד ההבנה של בעיות בלתי-כריעות משפיעה על עבודתם של מתכנתים ומפתחי אלגוריתמים בפועל?

נקודות לתשובת מודל (לשאלה: הוכח כי בעיית הריקות (E_TM) היא בלתי-כריעה, באמצעות רדוקציה מ-A_TM)

הנחה בשלילה: נניח ש-E_TM כריעה. כלומר, קיימת מכונת טיורינג R שפותרת את E_TM (R מקבלת <M> אם L(M) = ∅, ודוחה אחרת, ותמיד עוצרת).
מטרה: נבנה מכונת טיורינג D שפותרת את A_TM באמצעות R, ובכך נגיע לסתירה לאי-כריעות של A_TM.
בניית D:
1. D מקבלת קלט <M, w> (עבור A_TM).
2. D בונה מכונת טיורינג חדשה M' (שהיא פונקציית הרדוקציה f(<M, w>) = <M'>) באופן הבא:
  - M' מקבלת קלט x.
  - M' מתעלמת מ-x.
  - M' מריצה את M על w.
  - אם M מקבלת את w, אז M' מקבלת את x.
  - אם M דוחה או נכנסת ללולאה על w, אז M' דוחה או נכנסת ללולאה על x.
3. D מריצה את R על הקלט <M'>.
4. אם R מקבלת <M'> (כלומר, L(M') = ∅), D דוחה <M, w>.
5. אם R דוחה <M'> (כלומר, L(M') ≠ ∅), D מקבלת <M, w>.
הוכחת נכונות הרדוקציה:
- אם <M, w> ∈ A_TM (כלומר, M מקבלת w), אז M' תקבל כל קלט x. לכן, L(M') = Σ* ≠ ∅. במקרה זה, R תדחה <M'>, ו-D תקבל <M, w>.
- אם <M, w> ∉ A_TM (כלומר, M אינה מקבלת w), אז M' לעולם לא תקבל אף קלט x (היא תדחה או תיכנס ללולאה). לכן, L(M') = ∅. במקרה זה, R תקבל <M'>, ו-D תדחה <M, w>.
מסקנה: D פותרת את A_TM. מכיוון ש-A_TM ידועה כבלתי-כריעה, הגענו לסתירה. לכן, ההנחה ש-E_TM כריעה שגויה, ו-E_TM היא בעיה בלתי-כריעה.

מצאתם טעות או שחסר משהו?