בעית ארבע הצבעים

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

[swfobj src=”http://www.nikoli.com/swf/four_color_problem_001_en.swf”]
מפות נוספות

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

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

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

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

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

לקריאה נוספת: משפט ארבעת הצבעים בויקיפדיה

Tags: , , ,

3 Responses to “בעית ארבע הצבעים”

  1. גדל says:

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

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

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