קיום פיתרון

[ron369]

(ללא נושא)

אם באמת היית צריך, אני בטוח שהיית מוצא זמן. איכשהו.

 

[vinney]

../images/Emo6.gif גם נכון

 

[gil levi]

אני חושב שיש אלגוריתם לפתרון.

אלגוריתם BF, לא ישים עם סיבוכיות זמן מטורפת, אבל הוא עושה את העבודה: אפשר לכתוב תכנית מחשב P שמקבלת טקסט ופסוק לוגי ובודקת אם הטקסט הוא הוכחה של הפסוק. ניצור את כל הטקסטים האפשריים באורך עד 40^2 עם מילים באורך עד 40^2 וניתן לP לבדוק אם כל אחד מהם הוא הוכחה של הפסוק "השערת גולדבאך נכונה" או הוכחה של הפסוק "השערת גולדבאך אינה נכונה". אם אחד מהטקסטים הללו הוא הוכחה אז פתרנו. אחרת, נעשה את אותו הדבר עם טקסטים באורך עד 41^2 עם מילים באורך עד 41^2 ונמשיך באותו אופן.

 

[ron369]

ומי אמר שיש הוכחה?

 

[gil levi]

לירן.

בהודעה עם הכותרת "רון דווקא צודק".

 

[IP yuval]

זה שידוע שהיא או נכונה או לא נכונה

לא אומר בהכרח שאפשר להוכיח את אחת האפשרויות.

 

[ron369]

למען האמת, אני לא משוכנע

אולי גם זה נובע מגדל. נעביר את הנושא לפורום מתמ'?

 

[gil levi]

אני הבנתי שלירן התכוון

שניתן להוכיח או ניתן להפריך את השערת גודלבך. נחכה להבהרה שלו.

 

[yuvalmadar]

כך גם אני הבנתי

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

 

[gil levi]

מה ז"א "טענה נכונה"?

איך אתה יודע שהשערת גולדבך נכונה (כלומר, שאכן לכל מספר טבעי n קיימים שני ראשוניים p,q כך ש p+q=2n (מקווה שאני לא מתבלבל בניסוח))?

 

[גיל14]

אולי דווקא הטענה

"קיים n כך שלא קיימים ראשוניים p,q כך ש p+q=2n" נכונה, והיא הטענה הנכונה שאפשר להוכיח?

 

[yuvalmadar]

התכוונתי ל"ניתנת להוכחה או להפרכה"

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

 

[gil levi]

הבנתי.

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

 

[yuvalmadar]

טוב, אז אני אשאר בשקט

עד שאלמד לוגיקה ואגלה לאיזה מין מערכות מתייחס משפט השלמות של גדל.

(ולאן לירן נעלם?)

 

[gil levi]

כיוון חדש (יכול להיות שאני מקשקש).

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

 

[gil levi]

מחכה לתגובה של מתמטיקאי....

 

[ron369]

קיים אלגוריתם כזה? ../images/Emo2.gif

 

[gil levi]

אתה מתכוון לפרדוקס בנך-טרסקי

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

 

[ron369]

הלוגיקה הזו מעצבנת אותי

אתה יכול הסביר מה הקלט-פלט של האלגוריתם?

 

[gil levi]

אוקיי.

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