אני לוקח קורס קיץ בחישוביות, כדי להוריד מהעומס בשנת הלימודים הקרובה.
קיבלנו שאלה לא פשוטה בכלל, ואני לא ממש יודע איך להתמודד איתה.
אשמח להכוונה (ועדיף רק הכוונה, כך שברגע שאבין את הרעיון, אוכל לפתור בעצמי) לגבי השאלה.מדובר בשאלה 4, סעיף ג:
http://yairdombb.com/courses/comp2010s/Ex04.pdf
כמו כן, הגדרנו מכונת טיורינג כ"שביעייה" (Q,Σ,Γ,δ,q_0,q_acc,q_rej)
ולכן הקבוצה TM עבור הערכים 0,1,2 היא קבוצה ריקה (מפני שכל מכונה מכילה לפחות את המצבים q_0,q_acc,q_rej),
ויש צורך לתקן קצת את השאלה, ולהגדיר שבמקרים הספציפיים הנ"ל, הפונקציה BB מחזירה 0.
זה לא אמור לשנות לגבי סעיף ג', התיקון הוא רק בשביל הגדרת השלמות.
בכל אופן, גם עם ההדרכה, לא הצלחתי להבין איך לפתור את השאלה.
אני מניח שצריך להראות ש-M_BB מופעלת על עצמה היא המקסימום, ואז ניכנס למן פרדוקס רקורסיבי כזה... וזה יסתור את הגדרת השלמות.
אבל לא הצלחתי להבין איך להשתמש בזה.
תודה רבה, ושבת שלום.