עדיין בדיון

[vizini]

גם לכך יש פיתרון פשוט -

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

 

[שייח ספיר]

לא פתרת כלום

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

 

[vizini]

אה, אבל כאן אתה טועה.

איננו יכולים להחליט ש"עצירה" מוגדרת כמתן תשובה. ההבדל מאוד פשוט - אם B עוצר - F יכולה להתחיל לרוץ. אם B איננו עוצר (למרות שהדפיס תשובה) - F לעולם לא תרוץ ולכן הוספתה אחרי B היא חסרת משמעות. תחשוב על B כעל מערכת הפעלה. מערכת זו רצה בלולאה אינסופית, כאשר לכל קלט היא קוראת לתת שגרה שתתפל בה, ובסוף תת השגרה השליטה חוזרת למערכת ההפעלה. אין שום משמעות להוספת פונקציה שתרוץ אחרי שמערכת ההפעלה תסיים, כי היא לעולם לא תסיים. לכן אינך יכול להרחיב את B ע"י הוספת F בסיומה. F יכולה לרוץ על מחשב אחר, כמובן, לקבל קלט מ-B ולעשות איתו מה שליבה חפץ, אבל אז לא תחשב כאלגוריתם אחד יחד עם B, כלומר, הצירוף B+F איננו אלגוריתם במקרה זה. כך או כך, ההוכחה של פנרוז איננה ישימה במקרה זה. כלומר, מצאנו אלגוריתם שלגביו ההוכחה של פנרוז איננה ישימה, ולכן הוא עשוי להיות תודעתי. מש"ל.

 

[שייח ספיר]

לא.

אתה לא צריך לחכות ש-B תעצור. כל מה שאתה צריך לעשות זה לקחת את השורה (או השורות) בB שמגדירות שליחת פלט, ולהצמיד מיד אחריהם קריאה לF המקבלת את את הקלט של B כקלט. לחילופין, אתה יכול להגדיר מחדש את פונקציית הפלט (נגיד "printf") כך שתכיל בתוכה גם קריאה לF. בקיצור, די בשינויים טריוויאלים כדי להמיר את B ב-A.

 

[vizini]

לא.

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

 

[שייח ספיר]

שוב לא.

"...ואם היא עוצרת, B ממשיך ושוב התנאי מתקיים" - לא נכון. F גורמת בסוף ביצועה לטרמינציה סופית של האלגוריתם (halt). היא לא מחזירה את הבקרה לB.

 

[vizini]

היא לא יכולה.

אם היא נקראת כפונקציה מתוך B, היא לא יכולה לגרום לטרמינציה של B. עצירה שלה פירושה המשך של B.

 

[שייח ספיר]

מה פתאום?

אם למשל מימשת את האלגוריתם ב-C, יש לך פקודת exit (לא "return" או "break") שעוצרת את הפרוסס כולו. אם מדובר במכונת טיורינג, אחד המצבים מוגדר כ"עצור", ודי בכך ש-F עוברת למצב הנ"ל.

 

[vizini]

פתאום ורעמסס

פקודת exit לא גורמת למערכת ההפעלה לעצור. פקודת exit היא פונקצית שירות של מערכת ההפעלה, וגורמת פשוט לסיום של תוכנית ולהעברת הבקרה למערכת ההפעלה. אין שום פקודה שגורמת למערכת ההפעלה לעצור (בחלונות 98 יש כפתור קטן שאמור לעצור את מערכת ההפעלה, אבל גם הוא לא מצליח. הדרך היחידה שלי לעצור את מערכת ההפעלה הוא פשוט להוציא את כבל המתח...) לגבי מכונת טיורינג, אלגוריתם B שייך לתת קבוצה של מכונות טיורינג שלהם אין שום מעבר בטבלת המצבים למצב הסיום. אלגוריתם זה מפעיל את F כמו מכונת טיורינג אוניברסלית - הוא מסמלץ את מצבי F. בפרט, יש לו מצב שנקרא "סיום F". הוא יכול להגיע למצב זה, אך לא למצב הסיום של B. כאשר הוא מגיע למצב "סיום F " , F מסתיימת אך B ממשיך.

 

[שייח ספיר]

תות אנח עמון

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

 

[שייח ספיר]

טל"ח: מפיק קלט=מפיק פלט

 

[vizini]

תות? הנח המון...

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

 

[שייח ספיר]

"שבירת הכלים" במכונת טיורינג

היא פשוט המעבר למצב "עצור". קיום המצב הזה הוא חלק מהגדרת מכונת טיורינג. אינך יכול לבטל אותו. במקרה של מימוש ממוחשב, יש "שבירת כלים" אחרת, אבל כזו תמיד קיימת, אלא אם כן התודעה היא של אלוהים. אז אני מוכן לקבל שאלוהים הוא אלגוריתם. ומה עם השאר? B אולי מפיק את הפלט "לא", אלא שאתה ממיר את פונקציית הפלט (נגיד printf) בפונקציה F המדפיסה רק אם היא מקבלת הוראה להדפיס "כן", ובשאר המקרים חוזרת מבלי להדפיס דבר. כעת הפעל את המשפט על B+F. לחילופין, החלף את המלה "עוצר" לא ב-"מפיק פלט" אלא "מפיק את הפלט 'כן'". ואפשר להמשיך לשחק במשחק הזה עוד ועוד. לכל וורסיה של B שתציע אני אמצא את הטרנספורמציה המתאימה אותה לתנאי המשפט של פנרוז. השאלה היחידה היא מי יתעייף קודם.

 

[vizini]

אין שבירת כלים במכונת טיורינג.

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

 

[שייח ספיר]

כל מכונת טיורינג שתציע

אני יכול לסמלץ במכונת טיורינג אוניברסלית, ומכונה כזו כן מכילה מצב עצירה. כמו כן, גם אם המכונה שלך לא מגיעה למצב עצירה, המצב קיים (קיומו הוא חלק מהדרישות המגדירות מכונת טיורינג) ולכן F יכולה להגיע אליו. "אם הפונקציה F משקרת, אז בוודאי שהיא מפירה את התנאי של פנרוז" - מה זאת אומרת "משקרת"? איך פונקציה יכולה לשקר? התנאי של פנרוז, מוגדר מחדש, הוא: האלגוריתם A יתן פלט "כן" רק במקרים (אבל לא בהכרח בכל המקרים) בהם אלגוריתם הקלט איננו נותן פלט "כן". הוספת F איננה גורמת לאלגוריתם B+F לא לעמוד בתנאי, משום שכל מה שהיא עושה זה להעלים פלטים ששונים מ-"כן" (בפרט, להעלים "לא"). "זה משפט של ווסלי, אבל לא יכולתי להתאפק..." - בתור אלגוריתם אמין, עליך להתסתפק במשפטים של ויזיני

. __________________________________________

 

[vizini]

הצלחת לבלבל אותי.

B מדפיס כן אם הוא יודע ש C מדפיס כן, ולא אם הוא יודע ש C מדפיס לא או שהוא לא יודע. A מדפיס כן רק אם הוא יודע ש C לא מדפיס כן. כדי להפוך את B ל-B' מטיפוס A, יש להפוך כל כן של B ללא. שים לב, שאסור להפוך לא של B לכן, שכן אז עלול תנאי A לא להתקיים (כי B אומר לא גם במקרה שהוא לא יודע). המסקנה הראשונה היא ש B' הוא תמיד האלגוריתם הטריוויאלי, שאומר תמיד לא. אם B יודע את זה, האם הוא יכול לומר לא על B'? בוודאי. אז איפה הסתירה?

 

[שייח ספיר]

הצלחת לבלבל את עצמך.

"B מדפיס כן אם הוא יודע ש C מדפיס כן, ולא אם הוא יודע ש C מדפיס לא או שהוא לא יודע" - אבל לא על אלגוריתם שמזהה אלגוריתם שמוציא-קלט-נתון/עוצר מדברים אלא על אלגוריתם שמזהה אלגוריתם שלא-מוציא-קלט-נתון/לא-עוצר. זיהוי אלגוריתם שפולט "כן" אכן ניתן לביצוע באופן אלגוריתמי, ואף אחד לא טען אחרת אף פעם. מה שלא ניתן לזהות אלגוריתמית (אבל ניתן תודעתית) זה שאלגוריתם האלכסון שבהכרח לא פולט "כן". _______________________________________________

 

[vizini]

נו, וB לא יודע את זה?

אם A מדפיס לא על עצמו, B ידפיס לא על A. כלומר, B יודע שA מדפיס לא על עצמו, ואומר זאת. איפה הבעיה?

 

[שייח ספיר]

טוב. נעשה סדר.

גם אני התבלבלתי קצת, אז הנה אני מגדיר את הדברים מחדש. אתה צודק ש-B כפי שהגדרת אכן לא מובילה לסתירה. זה קורה משום שהדרישה ממנה היא למעשה חלשה יותר מהדרישה מ-A, עקב כך שהפלט שלה לא מאפיין במלואו את סוגי הפלט האפשריים כאשר היא רצה על עצמה. גם אם היא קובעת ש-C עוצר, עבור C שהוא B בעצמה, אין היא קובעת אם הוא עוצר עם פלט "עוצר" או "לא עוצר". כדי לצור מקרה דומה לזה של המשפט של פנרוז, אפשר להגדיר את הפלטים האפשריים של B כך: a- מדפיס: "לא עוצר" b- מדפיס: "עוצר עם פלט a" כעת הבעייה שקולה למקרה של A. אם נניח ש-C (האלכסון של B) עוצר נקבל סתירה, ועל כן C איננו עוצר, ולכן B איננה עוצרת ואיננה יכולה להכריע בבעייה שההוכחה הנ"ל מכריעה בה. בכל אופן, אפשר להציע גם פתרון אחר, פרט להגדרה מחדש של תנאי הפלט, וזה הוספת אלגוריתם F. אלגוריתם זה יתחבר לפונקצית הפלט של האלגוריתם וידאג לתקוע אותה בלולאה אינסופית אם הפלט המתקבל בה הוא "עוצר". כך B+F הופך בעצם ל-A ושלום על ישראל. ________________________________________________

 

[vizini]

סדר? עשית בלגן.

לאלגוריתם כלשהו C יש ארבע אפשרויות: עוצר או לא עוצר, מדפיס קלט או לא מדפיס. אלגוריתם B אמור להיות התודעה. הוא בעצמו לא עוצר על אף קלט, ומדפיס את מה שהוא יודע על אלגוריתם הקלט. המקרה שהוא לא יודע על אלגוריתם הקלט הוא כרגע לא מוגדר. עכשיו, איפה אתה רואה סתירה?