רדוקציה מTOT לINF

[Jimbryho]

רדוקציה מTOT לINF

קיבלנו כשיעורי בית לבנות רדוקציה מTOT (קבוצת מספרי התוכניות שעוצרות על עצמן) לINF. (קבוצת מספרי התוכניות שעוצרות על מספר אינסופי של קלטים) - TOT<=INF כל נסיונותיי בפתרון השאלה עלו בתוהו. תוכלו לכוון אותי בבקשה?

 

[vinney]

מה הבעיה לקחת פונקציה

שלכל X בTOT, ולכל קלט, תריץ את הX על עצמו?

 

[yuvalmadar]

חסר כיוון...

אמנם כל תוכנית מtot תותאם לtot ובפרט לinf על ידי הפונקציה הזו, אבל ההפך לא נכון - יש תוכניות שאינן שייכות לtot שתמונתן תהיה בtot בכל זאת. (למשל, תוכנית שעוצרת על עצמה בלבד. אני חושב שאפשר להוכיח שקיימת כזו עם משפט הפרמטר, אבל לא ניסיתי)

 

[vinney]

לא הבנתי

הרדוקציה שלי תתאים לכל תוכנית שעוצרת על עצמה תוכנית שעוצרת על כל קלט (לפחות זה מה שהתכוונתי שהיא תעשה...) זה לא מה שהוא רצה? ההיפך הוא לא נכון, לא כל תוכנית שעוצרת על קלט אינסופי בהכרח תעצור על עצמה, ולכן אם נפעיל את הפונקציה על תוכנית מINF זה בכלל לא בטוח שנגיע לפונקציה בTOT (למעשה, זה לא מסובך למצוא דוגמא נגדית פשוט) או שאני מתבלבל לחלוטין? שונא רדוקציות...

 

[yuvalmadar]

אני חושב שאתה מתבלבל

אבל קשה לי להצביע על מקור הבלבול. רק ליתר בטחון, אזכיר שוב את הגדרת הרדוקציה מקבוצה A ל קבוצה B: (בסימנים, B>=A) קיימת פונקציה חשיבה חלקית f כך שלכל x טבעי מתקיים:

x is in A if and only if f(x) is in B​

(שים לב שההגדרה לא סימטרית ביחס לA ולB למרות השקילות כיוון שf אינה חח"ע בהכרח) ורק ליתר בטחון, אזכיר גם את הגדרת TOT - קבוצת התוכניות שעוצרות לכל קלט. אז, ההתאמה שהצעת תתאים לכל תוכנית x שעוצרת על עצמה תוכנית שעוצרת לכל קלט. אם נתבונן בתוכנית שעוצרת על עצמה, אבל לא על כל קלט (כלומר, לא שייכת לTOT) - היא תותאם לתוכנית שעוצרת על כל קלט, אשר שייכת לINF. לכן, מצאנו x כך שf(x) שייך לINF וx אינו שייך לTOT, ולכן מדובר ברדוקציה. ובנוגע לרדוקציות, אני מסכים איתך.

עסק מסובך מאד! (ולצערי, אני לא חושב שהממ"ן שעשיתי בנושא חיזק את השליטה שלי בבניית רדוקציות במידה מספקת. אקווה שיהיו עוד רדוקציות מסוג זה בהמשך הקורס)

 

[shirbi]

שינית את ההגדרה של TOT.

במקור היה כתוב: קיבלנו כשיעורי בית לבנות רדוקציה מTOT (קבוצת מספרי התוכניות שעוצרות על עצמן) ועכשיו כתבת: ורק ליתר בטחון, אזכיר גם את הגדרת TOT - קבוצת התוכניות שעוצרות לכל קלט. כמובן שזה משנה את הפתרון. בנוסף " קיימת פונקציה חשיבה חלקית f כך שלכל x טבעי מתקיים:" למה f חלקית? עד כמה שאני יודע, היא אמורה להיות מלאה - כלומר מוגדרת לכל x.

 

[vinney]

אז למה הפונקציה שלי לא מתאימה?

אני עדיין לא מבין...

(אמרתי כבר שאני שונא רדוקציות?)

 

[shirbi]

מי אמר שהיא לא מתאימה?

לי היא נראית מצויינת, מלבד זה שאמרת שנפעיל אותה רק על כל X ב TOT. כל הרעיון זה שאפשר להפעיל אותה על כל X וכך לקבל שאם X ב TOT אז F של X ב INF ואם X לא ב TOT אז F של X לא ב INF.

 

[vinney]

נו, לזה התכוונתי

הכוונה שאם הX בTOT, התוצאה של הפעלת הפונקציה עליו תהיה בהכרח בINF

 

[vinney]

אם ורק אם, זאת אומרת ../images/Emo13.gif

 

[yuvalmadar]

רדוקציה נפלאה ../images/Emo13.gif

לא קראתי את הפירוש לשם TOT בדבריו של הכותב כי הנחתי שאני מכיר את המחלקה.

(בהנחה שהוא לא כתב את זה בטעות)

 

[yuvalmadar]

אה ../images/Emo12.gif

אז, השאלה היא למה התכוון כותב השאלה... אני מכיר את TOT כקבוצת התוכניות שעוצרות לכל קלט.

(מהמילה Total) וכמובן, אתה צודק בנוגע לחשיבות. היא צריכה להיות מלאה.

 

[shirbi]

אני לא מכיר אותה בכלל ../images/Emo13.gif

 

[yuvalmadar]

גם לומד באו"פ? ../images/Emo13.gif

ניסיתי להוכיח את זה בעצמי בממ"ן האחרון. (טוב, זה די מתבקש. נכונות השאלה נובעת מיידית מהתרגיל העוקב בספר, אז טבעי לפתור אותו פשוט

) אעתיק את תיאור רעיון הפתרון שכתבתי במקום אחר (לא בממ"ן): "הרעיון הוא שלכל קלט x, יש לבדוק האם התוכנית עוצרת עבור קלט t>=x כלשהו באמצעות הסטפר. (הוא בודק אם היא עוצרת על x לאחר צעד אחד, האם היא עוצרת על x או על x+1 לאחר שני צעדים, x,x+1,x+2 לאחר שלושה צעדים וכו') והרעיון הוא שהתוכנית הזו תעצור על כל קלט אם ורק אם התוכנית המקורית תעצור על מספר אינסופי של קלטים. (במילים אחרות, אם לכל x, יהיה מספר שגדול מx עבורו התוכנית תעצור)"