תורת החישוביות/כריעות שפות/תרגילים

סגירות RE לאיחוד בר-מניה

נניח קבוצה בת מניה של שפות $L_{1},L_{2},\ldots$, שכ״א מהן ב־RE. נניח שברשותנו פונקציה בת־חישוב $f$ אשר לכל מספר טבעי $i$ מייצרת את $\langle M_{i}\rangle$.

נסמן את איחודן כ:

$L=\bigcup _{i=1,2,\ldots }L_{i}.$

1. מדוע אי אפשר להראות באינדוקציה ש־$L\in RE$?
2. הוכח כי $L\in RE$.
3. האם החיתוך של השפות, $\bigcap _{i=1,2,\ldots }L_{i}.$ ב־RE ?

רמז לסעיף 2: נסה "לסמלץ" בבת אחת את כ״א מהשפות המרכיבות את $L$.

הפתרון

נבנה מ״ט אשר בהנתן מילה $x$ מבצעת לולאה חיצונית ופנימית.

1. בלולאה החיצונית, היא מייצרת אינדקס רץ $i=1,2,\ldots$
2. בלולאה הפנימית, באיטרציה ה$i$ של הלולאה החיצונית, היא מייצרת כ״א מ־$i$ המ״ט הראשונות, ומריצה כ״א מהן $i$ צעדים.

אם אחת מהמ״ט קיבלה את $x$, אז היא מחזירה שהמילה התקבלה, והמכונה הכוללת מקבלת.

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

שפה כריעה ניתנת למניה לקסיקוגרפית

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

הוכח: $L\in R$ אם ורק אם קיימת מ״ט המונה את כל המילים ב־L לפי סדר לקסיקוגרפי