בעית העצירה

[123W]

זה, וההוכחה שיש יותר מספרים ממשיים מאשר שלמים

 

[Deleted member 887]

מפתח web סופר מוכשר שמרוויח $200K בשנה צריך לדעת חשבון דיפרנציאלי לדעתך? נו באמת.

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

 

[לנצח נתהה]

זה, וההוכחה שיש יותר מספרים ממשיים מאשר שלמים

מה הקשר בין זה לבין הטענה שמחשב לא יכול לפתור כל בעיה ?(סתם מעניין אותי)

 

[adamshalev]

זה, וההוכחה שיש יותר מספרים ממשיים מאשר שלמים

מזכיר לי את זה.

 

[VaticanShadow]

מה הקשר בין זה לבין הטענה שמחשב לא יכול לפתור כל בעיה ?(סתם מעניין אותי)

שההוכחה לשתי הבעיות משתמשת בטיעון ליכסון

 

[לנצח נתהה]

שההוכחה לשתי הבעיות משתמשת בטיעון ליכסון

מודה שאין לי מושג למה הבעיה של גדל קשורה לטיעון ליכסון

 

[yotamd]

מודה שאין לי מושג למה הבעיה של גדל קשורה לטיעון ליכסון

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

הנה פוסט מעולה של גדי אלכסנדרוביץ על משפטי אי השלמות.
ואני ממליץ לקרוא גם את הערך על לכסון בויקיפדיה.

 

[123W]

מה הקשר בין זה לבין הטענה שמחשב לא יכול לפתור כל בעיה ?(סתם מעניין אותי)

לדעתי? הצורה שאתה חושב על הבעיה....

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

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

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

אה, וכל היופי פה, זה שאתה משתמש בכלים מתמטיים שילד בכיתה ה יכול להבין. עבור שתי ההוכחות.

 

[ברננקי]

למשל הסרטון הזה:
https://youtu.be/92WHN-pAFCs

הערת אגב: ממליץ מאוד לעיין בערוץ שלו, הוא אמנם כבר לא פעיל ויש בו סרטונים ספורים - אבל מגניבים מאוד. למשל הסברים יסודיים מאוד (ווזיואליים) על אלגוריתמי מיון. פלוס היוצר ישראלי.

 

[DERONDA]

שלום חבריי המלומדים,
האם מישהו כאן יודע להסביר לי את בעית העצירה באופן שאבין אותו? The halting problem.
תודה לעוזרים.

אני יכול לכתוב תוכנית ב C שמדפיסה למסך "hello" כל שניה,

ואתן לך רק את ה EXE להרצה.

איך תוכל להגיד לי אם התוכנית תסתיים מתי שהוא,או שהיא נידונה לרוץ לנצח?

נניח תחליט אחרי 900 שניות שהתוכנית אין סופית אבל היא בעצם מסתיימת אחרי 1000 שניות.

אולי תחליט שהתוכנית סופית, אבל היא אין סופית? תאלץ לצפות במסך לנצח

 

[Modric19]

אני יכול לכתוב תוכנית ב C שמדפיסה למסך "hello" כל שניה,

ואתן לך רק את ה EXE להרצה.

איך תוכל להגיד לי אם התוכנית תסתיים מתי שהוא,או שהיא נידונה לרוץ לנצח?

נניח תחליט אחרי 900 שניות שהתוכנית אין סופית אבל היא בעצם מסתיימת אחרי 1000 שניות.

אולי תחליט שהתוכנית סופית, אבל היא אין סופית? תאלץ לצפות במסך לנצח

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

 

[חיים 111]

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

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

 

[Modric19]

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

הכוונה שלי שבהודעה שלו הוא לא התייחס למה שאתה כותב בכלל אלא הסביר 1/3.
ושוב את ההמשך אני עדיין לא מבין אבל לא ויתרתי

 

[חיים 111]

מישהו כבר הסביר בעמוד הקודם. אנסה גישה קצת אחרת. אשתדל גם לפצל לחלקים.
א. קודם כל - הצגת הבעיה. אני ממשיך את הגירסא ש- @DERONDA הציג לבעית העצירה. אנחנו שואלים אם ניתן לכתוב תוכנת מחשב, שמקבלת תוכנה שנכתבה בשפת C ועברה קמפול, ומודיעה האם הרצה של הקוד הזה מסתיימת או לא (בגירסא הזו לתוכנה שאותה בודקים אין קלט. מריצים אותה, היא עשויה להוציא פלט או שלא, אבל מה שמעניין אותנו זה אם היא מסתיימת או לא). כאמור לא ניתן להשתמש בפתרון הפשוט של "נריץ ונראה", כי במקרה והתוכנה הנבדקת אכן לא מסתיימת, לעולם לא נקבל תשובה, ולא נדע אם עוד מעט היא כן מסתיימת. הדרישות מהתוכנה המחליטה הן שהיא תמיד תסיים ותתן תשובה, ואף פעם לא תיתקע בעצמה.
ב. לפני ההוכחה שאין פתרון לבעיה - יש סיפור על חכם סיני שטען שהוא יכול לדעת מה יש ביד של האדם. בא אליו נער עם פרפר ביד ושאל האם יש לו ביד פרפר חי או פרפר מת. ענה לו החכם בידך הדבר. החכם כאן בעצם התחמק ולא נתן תשובה. אם הוא היה מוכרח לתת תשובה של "חי או מת", הוא היה נכשל. הכיוון של ההוכחה דומה לשיטה של הנער. נביא לחכם (במקרה שלנו - התוכנה שיודעת לומר אם תוכנות אחרות עוצרות או לא) מקרה שבו כל תשובה שייתן תהיה שגויה. המסקנה תהיה שלא קיים "חכם" כזה.
ג. עד כאן הסתדרתי בלי סימנים. עכשיו נכניס אותם. לתוכנה המתיימרת לפתור את בעית העצירה ולהודיע על כל תוכנה אם היא מסתיימת או לא נקרא D. לתוכנה שנבנה נקרא H. עוד נקודה שחסרה לנו זה שתוכנות יכולות להריץ תוכנות אחרות, ולקבל את התוצאה שלהם (לא אכנס לפרטים הטכניים, אבל הרבה שפות תכנות תומכות בזה, כולל שפת C שבדוגמא שלנו). נזכור שתוכנה H רצה בלי קלט, ותוכנה D רצה עם קלט שהוא מסוג "תוכנה שרצה בלי קלט". עכשיו נציג את התוכנה H:
ד. התוכנה H בשלב ראשון תריץ את התוכנה D על H, כלומר תשאל את תוכנה D האם תוכנה H מסתיימת. אם תוכנה D עומדת בדרישות, היא תמיד תסיים ותיתן תשובה לתוכנה H. עכשיו, תוכנה H שמקבלת את התשובה מתוכנה D, תפעל הפוך ממה ש-D טענה שהיא תפעל.
פסאודו קוד לתוכנה H:
1. הרץ את התוכנה D על התוכנה H, ותבדוק מה התשובה.
2. אם התשובה היא "H מסתיימת", תיכנס ללולאה אינסופית.
3. אם התשובה היא "H לא מסתיימת", תסיים את ריצת התוכנית.
ה. מסקנה: הצלחנו להראות שיש שאלות שהחכם לא יכול לענות עליהם, כלומר אין בעולם חכם שיודע הכל...

 

[DERONDA]

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

עכשיו נניח שיש לך חבר גאון "ארתור" שמסוגל לקבל EXE או כל תוכנית אחרת ולהודיע לך אם היא עוצרת או לא.

תבקש מארתור לקבל את הוא עצמו !

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

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

כלומר בשני המקרים הגענו למסקנה שארתור גאון לא קיים למעשה

 

[חיים 111]

תבקש מארתור לקבל את הוא עצמו !

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

 

[Modric19]

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

למה התוכנה צריכה לפעול הפוך? לא מבין את הקטע הזה

 

[סולידי]

אני יכול לכתוב תוכנית ב C שמדפיסה למסך "hello" כל שניה,

ואתן לך רק את ה EXE להרצה.

איך תוכל להגיד לי אם התוכנית תסתיים מתי שהוא,או שהיא נידונה לרוץ לנצח?

מה ההבדל בין לקבל את המקור ב-C לבין לקבל את היצוג בשפת מכונה (EXE)? הבעיה היא אותה בשני המקרים.

 

[hepaxo]

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

למה התוכנה צריכה לפעול הפוך? לא מבין את הקטע הזה

הפתרון של @DERONDA מעולה.

יכול להיות אולי שקשה לך להבין הוכחה בשלילה? זה עניין חשוב בשביל ההוכחה.

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

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

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

מצד שני, אותה הוכחה בשלילה אתה יכול לאמר:
בוא נניח (בשלילה) שיורד גשם בישראל.
לכן, המצב באירופה הפוך, ולכן באירופה לא גשום. אבל רגע, אני יודע שבאירופה גשום. אז בעצם הגעת לנתון לא נכון -> ההנחה שלך שיורד גשם בישראל היא בהכרח שגויה כלומר בישראל לא גשום.

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

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

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

 

[חיים 111]

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

למה התוכנה צריכה לפעול הפוך? לא מבין את הקטע הזה

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