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

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

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

הגדרות

עריכה

הגדרה:

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

  1.  
  2.  


הגדרה:

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

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

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

עריכה

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

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

 

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

 

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


טענה:

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


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

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

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


 


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