בתשובה לתוהה, 15/12/06 10:16
ההוכחה הזאת פשוט דבילית 424727
אח של אייל • בתשובה לתוהה שבת, 16/12/2006, 3:26
יש לי אתגר בשבילך, שמראה כמה בעיית העצירה קשה. כתוב תוכנית שבודקת האם האלגוריתם הבא עוצר.

אלגוריתם יאללה_בלאגן
א. N=4
ב. בדוק האם N הוא סכום של שני מספרים ראשוניים.
ג. אם כן:
ג1. N=N+2
ג2. חזור לשלב ב.
ד. אם לא: הדפס "השערת גולבך שגויה" וסיים.

שים לב, יאללה_באלגן בודק את השערת גולדבך (כל מס' זוגי גדול מ 2 הוא סכום של שני ראשוניים). אם ההשערה נכונה (ואף אחד לא הצליח עדיין להוכיח או להפריך את זה), יאללה_באלגן לעולם לא יעצור. כך, שאם אתה מצליח להריץ את התוכנית שלך ו*לקבל תשובה נכונה*, פתרת את אחת הבעיות הקשות במתמטיקה. כל מה שנשאר הוא להראות את התשובה למתמטיקאי, ואז אתה תהיה אדם עשיר ומפורסם (בהנתן, כמובן, שלא תמות בשיבה טובה לפני שהתוכנית שלך תחזיר תשובה).

האם אתה מרים את הכפפה?
ההוכחה הזאת פשוט דבילית 424739
האייל האלמוני • בתשובה לאח של אייל שבת, 16/12/2006, 9:32
זה אמנם מראה שבעיית העצירה קשה, אבל "תוהה" לא חלק על זה, אם אני מבין נכון: הוא רק חלק על זה שהיא בלתי פתירה, או אולי אפילו רק על ההוכחות לכך שהובאו כאן.

זה אגב מעלה שאלה מעניינת (בעיניי). האם במדעי המחשב מוצאים לפעמים הוכחות לא-קונסטרוקטיביות לקיומם של אלגוריתמים?
ההוכחה הזאת פשוט דבילית 424772
אח של אייל • בתשובה להאייל האלמוני שבת, 16/12/2006, 17:53
התוהה הביא אלגוריתם שפותר את בעיית העצירה. אם כך, זה ממש בקטנה בשבילו להביא אלגוריתם שבודק מקרה פרטי מאד: האם יאללה_בלאגן עוצר. בתור התחלה, הוא יכול להביא את האלגוריתם הכללי שלו.

נראה לי שאולי ע"י מקרה פרטי, יהיה אפשר להמחיש לתוהה היכן הטעות שלו.
ההוכחה הזאת פשוט דבילית 424774
גדי אלכסנדרוביץ' • בתשובה לאח של אייל שבת, 16/12/2006, 17:57
הוא לא הביא אלגוריתם כזה, אלא רק הציע שיטת ''שיפוץ'' לאלגוריתם אפשרי. יש בצורת הניסוח שלו בעיות פורמליות, אבל הרעיון הבסיסי דווקא לגיטימי (הוכחנו שאי אפשר לפתור את בעיית העצירה - הטוען תהה האם ניתן לפתור אותה עבור כל קלט שאינו ''המכונה הקוראת, הקלט של המכונה הקוראת'')
ההוכחה הזאת פשוט דבילית 424775
אח של אייל • בתשובה לגדי אלכסנדרוביץ' שבת, 16/12/2006, 18:01
אני מקבל את התיקון. אבל למה שלא יתחיל במקרה הפרטי שלי? אם הוא לא רוצה להיות עשיר ומפורסם אני מוכן לקחת את העונש הזה על עצמי. שיעשה את זה רק בשביל האתגר.
ההוכחה הזאת פשוט דבילית 424776
אביב י. • בתשובה לגדי אלכסנדרוביץ' שבת, 16/12/2006, 18:45
אם הבנת למה הוא התכוון בדיוק, אתה מוכן לנסח במקומו את הטענה עם "התיקונים"? (אותך אני מבין)

מהי בדיוק "בעיית העצירה תג" עליה אנו מדברים? האם לא קל לבצע ממנה רדוקציה אל בעיית העצירה ה"רגילה"?
ההוכחה הזאת פשוט דבילית 424780
גדי אלכסנדרוביץ' • בתשובה לאביב י. שבת, 16/12/2006, 19:04
יותר משזו בעיה, זה "אתגר" - תוכיח לי שלא קיים אלגוריתם Q שפותר את בעית העצירה עם הקלטים M, x תחת ההנחה שאם אלגוריתם S כלשהו משתמש ב-Q הוא מעביר לו כקלט גם את המידע על עצמו ועל הקלט שהוא עצמו קיבל.

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

בהתחלה התוהה הציג גרסה פשוטה יותר של האתגר: להוכיח שלא ניתן לפתור את בעיית העצירה גם אם מגבילים את הקלטים להיות מהצורה M,x כאשר M שונה מ-x. אפשר להוכיח באופן ישיר שגם אלגוריתם לפתרון הבעיה הזו לא קיים (הראיתי איך קודם), אבל גם רדוקציה מבעיית העצירה לבעיה הזו (שים לב: לא בכיוון ההפוך) קל להדגים: אם קיבלת M ו-x תעביר אותם לאלגוריתם הפלאי אם M שונה מ-x. אחרת, שנה את M בצורה שתחזיר מכונה שקולה (למשל, תוסיף עוד מצב פנימי שלא מגיעים אליו אף פעם) ואז תעביר את הקלט לאלגוריתם הפלאי.
ההוכחה הזאת פשוט דבילית 424804
אביב י. • בתשובה לגדי אלכסנדרוביץ' יום א', 17/12/2006, 0:29
כן, כמובן שלא בכיוון ההפוך. אני קצת חלוד. תודה!
ההוכחה הזאת פשוט דבילית 424779
אלון עמית • בתשובה לגדי אלכסנדרוביץ' שבת, 16/12/2006, 19:04
רעיונות דומים צצים מדי פעם גם לגבי משפט גדל (אולי אפשר להכריע כל טענה פרט לטענות השקולות ל"אני לא יכיחה"? או פרט לטענות מתייחסות-לעצמן? או פרט לטענות מתייחסות-לעצמן-בעקיפין?)

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

התשובה המתוחכמת יותר היא שכבר יש, בכל המקרים, דוגמאות מאוד קונקרטיות של בעיות הכרעה או עצירה וכו' שהן בלתי-פתירות. לדוגמה, אם נדון רק במכונות טיורינג המנסות לפתור משוואות דיופנטיות בדרך הפשוטה ביותר (לסרוק פתרונות אפשריים), גם את בעיית העצירה עבור היקום המאוד מצומצם הזה לא ניתן לפתור. זה כבר משפט הרבה יותר קשה, אבל הוא (מה לעשות) גם נכון, והוא בוודאי הרבה יותר חזק מהטענה הנדונה: התוהה מנסה לסלק רק את האלכסון (מכונה=קלט), ואילו כאן סילקנו את האלכסון ועוד הרבה יותר (כמעט את כל המכונות וכמעט את כל הקלטים), ואפילו זה לא מספיק.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות