תורת החישוביות/כריעות שפות/משפט רייס: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
←מניה רקורסיבית של שפות בעלות תכונה: קישורים פנימיים, הרחבה |
|||
שורה 94:
כעת נראה שתנאים אלה מספיקים לכך שההחלטה ב-<math>RE</math>.
{{הוכחה|1=
להלן תיאור
נשים לב שמתנאי 3 נובע שישנה מכונה <math>Q_3</math> אשר בהנתן שפה סופית השייכת ל<math>S</math>, עוצרת בשלב כלשהו ומקבלת את השפה. המכונה <math>Q</math> משתמשת ב<math>Q_3</math>.
המכונה <math>Q</math> פועלת במספר לולאות מקוננות:
# בלולאה החיצונית ביותר, היא מקדמת אינדקס <math>i = 0, 1, 2, \ldots</math>. עבור כל <math>i</math>, היא מייצרת את המחרוזת ה-<math>i</math> ב[[w:סדר לקסיקורפי|סדר לקסיקורפי]].
# בלולאה פנימית יותר, עבור ערך <math>i</math> והמחרוזת ה-<math>i</math>, היא מפעילה את <math>M</math> למשך <math>i</math> שלבים. אם המילה מתקבלת, <math>Q</math> מוסיפה אותה לרשימת מילים ש-<math>M</math> מקבלת.
# בלולאה פנימית יותר, עבוררשימת המילים שהתקבלו ע"י <math>M</math> עד כה, המכונה <math>Q</math> מייצרת את כל תת-הקבוצות האפשריות של המילים שהתקבלו עד כה.
# בלולאה הפנימית ביותר, עבור ערך <math>i</math> ותת-קבוצה של מילים מתקבלות, המכונה <math>Q</math> מריצה את <math>Q_3</math> לשאול האם תת-הקבוצה שייכת ל<math>S</math>. אם כן, המכונה <math>Q</math> עוצרת בתשובה חיובית.
}}
| |||