בעית ארבע הצבעים היא בעיה במתמטיקה האומרת שניתן לצבוע כל מפה בעזרת ארבעה צבעים בלבד כך שלא יהיו שני שטחים שנוגעים זה בזה.
אתם מוזמנים להתנסות בצביעת מפה באופן כזה עם האפליקציה הזו:
[swfobj src=”http://www.nikoli.com/swf/four_color_problem_001_en.swf”]
מפות נוספות
הבעיה הזו עניינה אותי במיוחד, בגלל שהיא מקשרת בין עולם המתמטיקה לעולם המחשבים.
בשנת 1976 חוקרים מאוניברסיטת אלנוי הצליחו להוכיח את המשפט.
הם הוכיחו זאת על ידי פירוק הבעיה ל1936 תת-בעיות קטנות ובדיקת כל אחת מהן בנפרד במחשב, הרצה שנמשכה מספר ימים.
החיבור בין מתמטיקה למחשבים הוא הכרחי, אך לא טבעי. החוקרים בשני התחומים הם בעלי מנטליות שונה לחלוטין. למשל מחקר חדש במתמטיקה צריך לעבור תהליך של חודשים עד שנים של בדיקה על ידי מומחים לפני שהוא מפורסם, לעומת זאת מחקר במחשבים שיקח לו יותר מחודש להתפרסם עלול לאבד רלוונטיות.
הפער הקשה לגישור הזה גרר הרבה ביקורת על ההוכחה מצד מתמטיקאים.
שתי הטענות שאתייחס אליהן הן:
ההוכחה לא תקפה – מתמטיקה היא מדע מדויק, הוכחה צריכה להרשם באופן שניתן לעבור על כל פרט שלה, אסור שמחשב יבדוק אותה כי אפילו אם קיים סיכוי של 0.00001% לטעות (בין אם באלגוריתם, בהקלדה, במימוש של המחשב או טעות מכנית שכן מחשב הוא מכונה מבוססת זרם חשמלי) אז זו לא הוכחה מתקבלת. גם אם נבדוק את האלגוריתם ונריץ על המון מחשבים, וניתן למחשבים לבדוק אחד את השני, מאחר ולעולם אנשים לא יוכלו לעבור שלב שלב על ההוכחה כולה היא לא תקפה.
ההוכחה לא יפה – הרבה מתמטיקאים התאכזבו לגלות שכך הוכח המשפט, מאחר ובדרך כלל הוכחה של משפט מתמטי מלווה בשימוש במספר כלים ממספר תחומים שבאופן מפתיע משתלבים יחד. בדרך כלל מעצם ההוכחה מקבלים תובנות חדשות שאינן נובעות מעצם המשפט שהוכח לבדו. בהוכחה שמבוססת על בדיקת המון מקרים אחד אחד זה לא קורה.
אני, שמגיע מתחום המחשבים, מתנגד נחרצות לטענות האלו, על סף האשמת המתמטיקאים בטכנופוביה (בלי הכללות, הרבה מהם כן מקבלים את ההוכחה)
לטענתי:
ההוכחה כן תקפה – אנחנו יודעים איך מחשב עובד, ונוכל לבדוק את ההוכחה שוב ושוב ככל שהטכנולוגיה תשתפר ולכן יחסית אפשר לסמוך עליו. כשאני אומר יחסית, אני מתכוון לעומת מכונות מבוססות אינטרקציות כימיות אקראיות, שאנחנו לא מבינים איך הן עובדות, אנחנו יודעים בוודאות שבמקרים מסוימים תפיסת המציאות שלהן שגויה, ורוב ההוכחות המתמטיות בוצעו על ידן: בני האדם.
ההוכחה כן יפה – ברגע שהצלחנו להוכיח בעיה מתמטית בעזרת מחשב, נפתח בפנינו עולם חדש שלם של גישה לבעיות מתמטיות, אילו עוד בעיות אפשר להכריע באופן דומה? איך פותרים בעיות מורכבות יותר?
חוץ מזה שעל מנת להצליח לפתור בעיה מתמטית עם מחשב, צריכים לעשות שימוש לא צפוי בידע ממקומות שונים של מדעי המחשב, ומקבלים תובנות חדשות על שימוש באלגוריתמים.
נושא בעית ארבע הצבעים היווה נקודה מרכזית בנוגע לתפיסה שלי במתמטיקה, כך לראשונה נחשפתי לעובדה שתקפות של הוכחה מתמטית הוא נושא בר וויכוח. אני מקווה לשוב לדון על תופעה מעניינת זו בפוסטים עתידיים.
לקריאה נוספת: משפט ארבעת הצבעים בויקיפדיה
Random Page
זה לא שמתמטיקאים לא מבינים במחשבים, היסטורית, המחשב פותח ע”י מתמטיקאי. מדעי המחשב הוא תת-ענף של מתמטיקה שימושית.
אם תעשה קורס בשיטות נומריות, אתה תבין יותר טוב איך מחשב עובד. מחשב לא שונה מתופעה כימית או אקראית אגב… כי התהליכים האלה מתרחשים בו. הוא לא דטרמיניסטי , להיפך מכשיר קוונטי. אתה הרי לא יכול לייצג מספר עשרוני במחשב בצורה חד-חד-ערכית.
כי הכל תלוי במס’ הביטים שלך (דיוק של 64ביט לעומת דיוק של 8ביט) לדוגמא… בכל אופן בגלל שמבינים כל כך טוב איך המחשב בנוי ההוכחה הזאת בעייתית.