שאלה על מכונות טיורינג.

[gil levi]

שאלה על מכונות טיורינג.

נתקלתי בה בנסיון לבנות רדוקציה. יש לי מכונת טיורינג M ואני רוצה לבנות מכונת טיורינג M2 כך ש:

∀x≠ε M(x)=M2(x) and M2(ε)=17​

האם מותר לי לעשות זאת? נדמה לי שלא, כי יכול להיות שהכרחי שM2(ε) zzz יהיה משהו אחר (לא 17) כדי שהתנאי החלק הראשון של התנאי יתקיים, אבל אני לא בטוח. מישהו יכול לעזור? תודה מראש.

 

[vinney]

ניסיתי לישון על זה ולא נרדמתי

תן דוגמא למקרה בו קלט אחד משפיע על תוצאה של קלט אחר. לא כל כך הבנתי את המשפט הזה : "יכול להיות שהכרחי שM2(ε) zzz יהיה משהו אחר (לא 17) כדי שהתנאי החלק הראשון של התנאי יתקיים"

 

[gil levi]

תודה על ההתייחסות.

אנסה לתת דוגמא בכווים כללים למ"ט M2 שבה M2(ε)!=17 וזה משפיע על התוצאה עבור קלטים אחרים: אם הסרט ריק, המכונה מחזירה 3 בכל מצב שהיא. בהתחלה M2 בודקת מה התו האחרון בסוף המילה. אם הוא 1 היא עוצרת. אם הוא 0 היא מוחקת אותו, נעה שמאלה ("אחורה") ועוברת למצב q_1. במצב q_1 היא מוחקת את כל התווים במילה עד שהסרט ריק ואז היא מחזירה 3. אני רוצה להגדיר מ"ט M1 כך שעבור כל דבר ששונה מε היא תחזיר את מה שM2 תחזיר, ועבור ε היא תחזיר 17. לא היה ברור לי אם אפשר לעשות זאת, כי אם אני אריץ את M2 על 110 אז היא תחזיר 3 כי עבור ε היא תחזיר 3, אבל אני דורש שM1 תחזיר 17 על ε. עכשיו נראה לי שכן אפשר לעשות זאת, גם במקרה כללי: M1 תחזיר 17 אם בתחילת הריצה הסרט ריק, ובכל מצב אחר שבו הסרט התרוקן היא תעבור למצב חדש שבו תחזיר את מה שM2 הייתה מחזירה. זה נכון?

 

[vinney]

110 בדוגמא שלך זה לא מילה ריקה

התוספת שאמרת נשמעת הרבה יותר הגיונית - ε זה אומר שהסרט כולו ריק, אם הסרט לא ריק והמכונה מרוקנת אותו - זה לא מקרה של ε, והM2 אמורה לתת אותו דבר שM1 נותנת, לכן נראה לי שמה שכתבת בסוף זה נכון, ואילו הדוגמא שנתת בהתחלה - לא ממש קשורה. תקן אותי אם אני טועה זאת אומרת

 

[gil levi]

לדעתי אתה צודק. תודה רבה.

 

[gil levi]

שאלה נוספת במודלים חישוביים.

השאלה בתמונה.

 

[gil levi]

והנה הפתרון, שאני לא מבין.

הפתרון בתמונה. אני לא מבין את ההוכחה שהשפה לא ב CO-RE. נסמן את הבעיה בL. משתי הרדוקציות נובע ש L לא בRE ושL לא בR, אבל איך זה מוכיח שL לא בCo-RE? תודה מראש.

 

[shirbi]

נסיון להסבר:

אנחנו יודעים שבעיית העצירה, HP, המקבלת מכונה וקלט עבורה ואומרת אם המכונה עוצרת על הקלט, לא נמצאת ב Co-RE. כלומר, עבור זוג (מכונה M וקלט עבורה X) אין בעיה לבנות מכונה שתענה "כן" אם המכונה M עוצרת על X אולם לא ניתן לבנות מכונה שתענה "לא" אם המכונה M לא עוצרת על X. כעת נראה רדוקציה: נניח שניתן לפתור את הבעיה מההודעה הקודמת שלך, באמצעות מכונה M2, ונראה כיצד לבנות מכונה M3 שמקבלת מכונה M וקלט X, ועונה "לא" אם M לא עוצרת על X. המכונה M3, בהינתן M ו X תקרא ל M2 ותיתן לה קלט את M, את X ואת 1, ואם היא עוצרת, אז M3 עונה "לא". כעת, אם M לא עוצרת על X אז המכונה M2 תעצור ולכן נוכל להשיב "לא".

 

[gil levi]

תודה, אבל לא הבנתי משהו.

נניח שהבעיה C אינה בCO-RE וקיימת רדוקציה מיפוי: C≤B. מדוע מכאן נובע שB אינה בCO-RE? תודה מראש.

 

[shirbi]

מה פירוש "גדול שווה"?

 

[vinney]

זה סימן שניתן לעשות רדוקציה, לא?

 

[shirbi]

ממי למי?

B גדול שווה ל C אומר שבהינתן פיתרון לבעיה B אפשר לבנות פתרון לבעיה C או להפך?

 

[vinney]

להיפך

אני חושב, זה תמיד בילבל אותי

 

[gil levi]

B גדול שווה C

אומר שניתן לבנות רדוקציה של C לB , כלומר: מכריעות של B נובעת כריעות של C. טריק לזכור זאת: אם B גדול שווה לC אז B יותר "קשה" מC, לכן אם B כריעה אז בוודאי גם C כריעה.

 

[vinney]

כן, נשמע הגיוני

זה עדיין כל הזמן מבלבל אותי

 

[shirbi]

ובכן...

CO-RE זה אוסף כל הקבוצות X, כך שלכל קבוצה X קיימת מ"ט M כך שלכל קלט x, אם x שייך ל X אז M עונה ש x שייך ל X או ש M לא עוצרת בכלל, ועבור כל קלט x שלא שייך ל X, המכונה M עונה ש x לא שייך ל X. מה אומרת הרדוקציה? שקיימת מכונת טיורינג M2 שמקבלת כקלט x כך שאם x שייך ל C, אז הפלט הוא y ששייך ל B, ואם x לא שייך ל C אז הפלט y לא שייך ל B. כעת, נניח ש B נמצאת ב CO-RE ואנחנו מכירים את המכונה המתאימה לה, M3. M3, על קלט x שלא שייך ל B תמיד עוצרת ועונה שהוא לא שייך ל B ועל קלט x שכן שייך ל B, או שהיא עוצרת ואומרת שהוא שייך ל B או שהיא לא עוצרת כלל. כעת, נראה כיצד לבנות מ"ט טיורינג M4 שבהינתן x, אם x שייך ל C אז היא אומרת שהוא שייך ל C או שהיא לא עוצרת, ואם הוא לא שייך ל C, אז היא עוצרת ואומרת שהוא לא שייך ל C: המכונה M4 תמיר את הקלט x ל y באמצעות המכונה M2 ואז תריץ את M3 על y ותענה כמוה. התוצאה תהיה ש M4 תעצור ותדחה את x אם ורק אם x לא שייך ל C. אם x כן שייך ל C אז היא לא תעצור או שתעצור ותקבל את x. כלומר M4 מראה ש C היא כן בCO-RE, בסתירה לנתון. לכן לא קיימת המכונה M3, כלומר הבעיה B לא נמצאת ב CO-RE.

 

[gil levi]

גדול אתה. תודה רבה!

 

[gil levi]

שאלה די קלה על כריעות.

האם הבעיה הבאה כריעה: קלט: מכונת טיורינג M ומחרוזת X? שאלה: האם M עוצרת על X וגם

זוגי? ברור לי שהיא לא כריעה, אבל אני לא מצליח להוכיח זאת. ניסיתי לבנות רדוקציה מHALT: בהנתן קלט (X,M) לHALT, אם

זוגי אז הקלט לבעיה שלנו יהיה (X,M), אבל איך מטפלים במקרה ש

אי זוגי? תודה מראש.

 

[shirbi]

תבחר בשפה אחרת בשביל הרדוקציה

כך למשל את השפה: אוסף כל המכונות שלא עוצרות על המילה הריקה. בעייה זאת היא לא כריעה ואין לך בעיה לעשות רדוקציה אליה.

 

[gil levi]

תודה.