תורת החישוביות/כריעות שפות/אי-הפרדתיות רקורסיבית
נניח שברשותנו שפה כלשהי, L. אם נרחיב אותה מספיק, בוודאי שנגיע בשלב כלשהו לשפה כריעה. ככלות הכל, כל שפה L מקיימת , ו היא בודאי שפה כריעה (ע״י מ״ט שבצעד הראשון עוברת למצב מקבל). הדבר מעלה את השאלה הבאה. נניח שיש שתי שפות זרות, ו. האם אפשר להרחיב את לשפה כריעה , מבלי להשתמש במילים מ־, כלומר ש־ ו־ תהינה זרות זו לזו?
כעת נראה שישנן שפות שאי אפשר להפריד אותן כך.
הגדרות
[עריכה]
הגדרה: נאמר ש מפרידה רקורסיבית את השפות , אם: |
הגדרה: נאמר שהשפות נתנות להפרדה רקורסיבית אם"ם קיימת שפה כריעה המפרידה אותן. |
נשים לב שהמושג "נתנות להפרדה רקורסיבית" אכן סימטרי. אם"ם ו נתנות להפרדה רקורסיבית, כך גם ו. נניח שישנה שפה רקורסיבית המכילה את והזרה ל. נגדיר את , ונשים לב ש גם היא כריעה, וכן שהיא מכילה את וזרה ל.
דוגמה: אי הפרדתיות שפת האלכסון מ"משלימתה"
[עריכה]נראה כעת דוגמה לשפות שאינן נתנות להפרדה רקורסיבית.
נגדיר את השפה באופן דומה לשפת האלכסון:
ואת כ"משלימתה"
(נשים לב שייתכן ש, מפני שישנן שפות שהפעלתן על קידודיהן אינה מסתיימת כלל, ולכן אין מדובר ממש בשפה משלימה).
טענה: ו אינן נתנות להפרדה רקורסיבית. |
הוכחה: צורת ההוכחה מזכירה מעט את זו שבעיית העצירה אינה כריעה.
נניח על דרך השלילה שקיימת שפה המפרידה בין השפות, ונניח ש היא מ"ט המכריעה שפה זו. מה ערכה של ?
- אם ערכה הוא accept, אז לפי ההגדרת , . מצד שני, המ״ט מכריעה את ולכן נובע , אך זו סתירה כי .
- באותו אופן, אם ערכה הוא reject, אז לפי ההגדרת השפה , ,ומכיוון ש־ מוכלת ב־, גם , וזו סתירה כי המ״ט שמכריעה את ענתה בדחיה.
הפרק הקודם: משפט רייס |
אי-הפרדתיות רקורסיבית | הפרק הבא: משפט הרקורסיה |