תורת החישוביות/כריעות שפות/אי-הפרדתיות רקורסיבית

מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
קפיצה לניווט קפיצה לחיפוש

נניח שברשותנו שפה כלשהי, L. אם נרחיב אותה מספיק, בוודאי שנגיע בשלב כלשהו לשפה כריעה. ככלות הכל, כל שפה L מקיימת , ו היא בודאי שפה כריעה (ע״י מ״ט שבצעד הראשון עוברת למצב מקבל). הדבר מעלה את השאלה הבאה. נניח שיש שתי שפות זרות, ו. האם אפשר להרחיב את לשפה כריעה , מבלי להשתמש במילים מ־, כלומר ש־ ו־ תהינה זרות זו לזו? שפות נתנות להפרדה רקורסיבית

כעת נראה שישנן שפות שאי אפשר להפריד אותן כך.

הגדרות[עריכה]

הגדרה:

נאמר ש מפרידה רקורסיבית את השפות , אם:


הגדרה:

נאמר שהשפות נתנות להפרדה רקורסיבית אם"ם קיימת שפה כריעה המפרידה אותן.

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

דוגמה: אי הפרדתיות שפת האלכסון מ"משלימתה"[עריכה]

נראה כעת דוגמה לשפות שאינן נתנות להפרדה רקורסיבית.

נגדיר את השפה באופן דומה לשפת האלכסון:

ואת כ"משלימתה"

(נשים לב שייתכן ש, מפני שישנן שפות שהפעלתן על קידודיהן אינה מסתיימת כלל, ולכן אין מדובר ממש בשפה משלימה).


טענה:

ו אינן נתנות להפרדה רקורסיבית.  


הוכחה: צורת ההוכחה מזכירה מעט את זו שבעיית העצירה אינה כריעה.

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

  1. אם ערכה הוא accept, אז לפי ההגדרת , . מצד שני, המ״ט מכריעה את ולכן נובע , אך זו סתירה כי .
  2. באותו אופן, אם ערכה הוא reject, אז לפי ההגדרת השפה , ,ומכיוון ש־ מוכלת ב־, גם , וזו סתירה כי המ״ט שמכריעה את ענתה בדחיה.


מש"ל.PNG


הפרק הקודם:
משפט רייס
אי-הפרדתיות רקורסיבית הפרק הבא:
משפט הרקורסיה