לדלג לתוכן

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

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

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

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

הגדרות

[עריכה]

הגדרה:

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


הגדרה:

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

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

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

[עריכה]

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

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

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

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


טענה:

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


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

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

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



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