סיוע בפתרון שאלה

[theuser1]

סיוע בפתרון שאלה

שלום לכל המדמ"חניקים! אני קורא פסיבי של הפורום, זה זמן מה (יחסית לגילו

). יש לי תרגיל שאני צריך להגיש, ואני די תקוע, אשמח לעזרה! נתון קלט: תוכנית Q האם התוכנית Q מחשבת את הפונקציה f=y^2 הוכח שהאלגוריתם לא-כריע הכיוון שאני חושב עליו זה רדוקציה לבעיית העצירה. אבל זה שתוכנית מחשבת y^2 לא אומר שהיא עוצרת! וגם אם כן, אם היא תעצור עם פלט אחר, זה לא אומר שהיא "לא עצרה". תוכלו בבקשה לדחוף אותי בכיוון הנכון?

 

[DadleFish]

אני חושב שהכיוון הנכון הוא

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

 

[theuser1]

זה שהקלט אינסופי לא אומר שבעיה

לא כריעה. לדוגמא, אלגוריתם שמחשב x/2. הוא בוודאי כריע, למרות ש-x יכול להיות אינסוף (גם בעוצמה א) מספרים.

 

[DadleFish]

אבל זו לא השאלה,

השאלה היא לא "האם אלגוריתם שמחשב x/2 הוא כריע", אלא "האם התוכנה הנתונה היא אלגוריתם שמחשב x/2 (או x^2, לא משנה)".

 

[theuser1]

אז איך אתה מוכיח אי-כריעות

של הבעיה המקורית? (זו השאלה)

 

[DadleFish]

זה מה שכתבתי בתשובה הראשונה

זו לא הוכחה פורמלית, אבל אולי רעיון כללי. חזרה 4 שנים אחורה לקורס חישוביות זה לא בתכנון שלי לחצי השנה הקרובה

 

[vinney]

כמו שאהד כבר כתב

בעיות כאלה תמיד מסתכמים ברדוקציה לבעית העצירה. אם בדרך פלא בעזרת הנחת הכריעות של האלגוריתם אתה פתאום פותר את בעית העצירה, אז ההנחה כנראה שגויה והאלגוריתם לא כריע.

 

[Fingertip]

נראה לי טריוויאלי...

אבל אולי אני טועה. בהינתן אלגוריתם A כזה, נוכל בקלות לפתור את בעית העצירה: בהינתן תכנית P וקלט x נריץ את A על האלגוריתם: 1) הרץ את (P(x. 2) החזר את x². ונחזיר את התשובה המתקבלת. נראה שהאלגוריתם נכון: עצירה: בנינו אלגוריתם (זה בוודאי עוצר, לא?) והאלגוריתם A עוצר לפי ההנחה ולכן האלגוריתם שלנו יעצור. נכונות חלקית: מכיוון שאם P לא עוצר על x לעולם לא נגיע ל-2 וממילא לא נחזיר x², ומכיוון שאם P עוצר על x הרי שבשלב כלשהו נחזיר x², הרי שהתשובה לשאלה "האם האלגוריתם מחזיר x²" זהה לתשובה "האם P עוצרת על x" וממילא קיבלנו פתרון לבעית העצירה. אולם ידוע לנו שבעית העצירה אינה כריעה, וממילא הנחת השלילה שגויה ולא קיים אלגוריתם A לבעיה הנתונה, ולכן הבעיה אי-כריעה, כמו שצריך להוכיח. מקווה שעזרתי, אהד.

 

[theuser1]

כן../images/Emo70.gif

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