אני אנסה להסביר. אזהרה - ארוך. אני אניח שיש לך איזהשהו ידע בתכנות. אם לא אז אתה מוזמן לשאול (אבל אני מודה שאני לא בטוח שאפשר להסביר את זה בלי להבין בכלל קוד).
כתבתי בפסודו-קוד בעברית, אני לא מצליח ליישר את הטקסט לכיוון השני ולכן קוד באנגלית מתחרבש.
בכל מקרה, אם משהו לא ברור - אני אנסה להסביר עוד. אשמח לפידבק על מה היה לא ברור.
ה-setting: יש מושג שנקרא מכונות טיורינג. ההגדרה המדויקת שלו לא חשובה, אבל בעצם אפשר לחשוב עליו בתור תוכנה. אבל במקום תוכנה רגילה שרצה על איזה מחשב, למכונת טיורינג אין מגבלות זיכרון, והיא יכולה לרוץ כמה זמן שהיא צריכה.
לשם פשטות, מה שעושים לתוכנה הזאת זה שמזינים לה איזה מחרוזת x (פשוט איזהשהו טקסט), ומפעילים אותה. התוכנה אז רצה, ומחזירה "כן" או "לא".
הנה דוגמה: נניח שהתוכנה שלי מקבלת טקסט באנגלית מחזירה "כן" אם מספר אותיות האהו"י הוא זוגי, ו-"לא" אחרת. הנה דוגמה לקוד של התוכנה הזאת:
1. אתחל משתנה x=0.
2. עבור כל אות letter בקלט:
2א. אם letter בקבוצה [a,e,i,o,u] אז x=x+1.
3. [בסיום הלולאה] אם x==0 (mod 2) החזר "כן", אחרת החזר "לא".
ניתן לשים לב, שלפעמים תוכנות לא עוצרות. הנה דוגמה לקוד של מכונת טיורינג נוספת:
1. אתחל משתנה x=0.
2. אתחל משתנה pos = 1
3. כל עוד pos קטן יותר מאורך הטקסט:
3א. אם האות במקום ה-pos היא בקבוצה [a,e,i,o,u] אז x=x+1.
3ב. אחרת pos=pos+1.
4. [בסיום הלולאה] אם x==0 (mod 2) החזר "כן", אחרת החזר "לא".
מה הבעיה בדוגמה השניה שלי? כשאני אריץ אותה על קלט שיש בו אות אהו"י (למשל הקלט "hello"), הקוד יכנס ללולאה באות h, ואז ימשיך לעוד סיבוב באות e.
אבל בסיבוב השני של הלולאה לא נגיע לשורה 3ב (כי האות e היא אות אהו"י. לכן פשוט נעשה x=x+1) ולכן לא נקדם את pos והתוכנה שלנו לא תעצור לעולם.
עכשיו, תוכנות שלא עוצרות על קלט הן בעיה קלאסית שהיינו רוצים להמנע ממנה. טכנית, אם חיפשת טקסט בגוגל ואיכשהו המנוע לא עצר לעולם - אז לעולם לא תקבל תשובה, תעזוב את גוגל, ותלך למנוע חיפוש אחר. בפועל, גוגל פשוט יכולים להחליט שאם התוכנה שלהם לא עצרה תוך 3 שניות, אז היא פשוט תגיד לך שאין תוצאות. אבל מניין לך שאם היינו נותנים לגוגל עוד שניה, אולי מנוע החיפוש כן יעצור וייתן לך תשובה?
לכן
בעיית העצירה היא הבעיה הבאה: תמצא אלגוריתם (דהיינו, כתוב קוד), שמקבל כקלד קוד של תכנה (אחרת) C, וקלט לתוכנה הזאת X. האלגוריתם צריך לעצור תמיד ולהגיד "כן" אם הקוד C עוצר כשמכניסים אליו את הקלט x, ו-"לא" אם הקוד C לא עוצר כשמכניסים אליו את הקלט X.
אפשר להשתעשע ולנסות לכתוב תוכנה כזאת. נגיד בדוגמה שלי, הבעיה הייתה שיש מצבים ש-pos לא מתקדם. אולי אני יכול לבנות איזה אלגוריתם שסורק את הקוד ומוצא כאלה לולאות בעייתיות? שאלה טובה. יכול להיות שמקרים פשוטים הייתי יכול לגלות, אבל באופן כללי התשובה היא
שלא.
יש משפט מתמטי של אלן טיורינג שאומר שאי אפשר לכתוב קוד שיגלה אם קודים אחרים עוצרים או לא.
למה? ובכן יש פה התחכמות לוגית כזאת. לפני שאציג אותה, אולי אציג קודם את "בעיית הספר" (יעני מעצב שיער, לא book). היא לא קשורה ישירות לכל מה שכתבתי קודם, אבל היא מציגה בעייתיות לוגית מסוימת שתחזור בהוכחה. מציע לקרוא כמה פעמים כי הלוגיקה מבלבלת...
בעיית הספר: בכפר נידח בן 100 תושבים יש ספר. נקרא לו מנשה. ידוע שמנשה הספר מספר רק את כל מי שלא מספר את עצמו. נשאלת השאלה - האם מנשה הספר מספר את עצמו (כלומר את מנשה)?
אם הוא
כן מספר את עצמו יש פה סתירה. הרי ידוע שמנשה מספר
רק את כל
מי שלא מספר את עצמו.
אוקיי... אז סימן שמנשה
לא מספר את עצמו. אבל, הרי ידוע שמנשה מספר את
כל מי שלא מספר את עצמו. לכן הוא צריך לספר את עצמו.
קיבלנו - פרדוקס!
לכן המסקנה שלנו כשומעים זה שמי שסיפר לנו את הסיפור על הכפר כנראה משקר. ומתמטית המסקנה היא
שלא יכול להיות שקיים ספר כזה.
גם אלן טיורינג חשב על הבעיה הזאת, והוא השתמש בה כדי להראות שכמו שאין ספר שמספר את מי שלא מספר את עצמו, אין גם תוכנה שאומרת אם הקוד שלך עוצר על פלט מסוים או לא.
מדוע? נניח הייתה לנו תוכנה כזאת, נקרא לא halt. בואו נביט בתוכנה הבאה (שנקרא לה halt2) שמקבלת קלט x:
1. הרץ את halt כשהקוד שאתה מקבל הוא x וגם הקלט הוא x (כלומר אנחנו בודקים אם הקוד של התוכנה עוצר כשהוא מקבל כקלט את עצמו).
2. אם halt אמרה "לא" אז תחזיר "לא" ותסיים.
3. אתחל משתנה x=1
3. אם halt אמרה "כן" אז כל עוד (x<2):
3א. x=x-1.
4. [בסיום הלולאה] החזר "כן".
נראה שיש פה טעות, נכון? בניתי תוכנה שעושה בערך את מה ש-halt עושה: אם halt אמרה "לא" על C=x ו-X=x אז halt2 גם אומרת "לא". אבל אם halt אומרת "כן", אז halt2 לא תגיד כן. היא תכנס פשוט ללולאה ולא תעצור. נראית כמו תכנה די מטופשת.
אבל מה יקרה אם נכניס ל-halt2 את הקוד של halt2? האם halt2 יעצור או לא?
1. אם halt2 יעצור - סימן ש-halt (הרגילה) אמרה "לא", כששאלנו אותה האם halt2 תעצור על halt2. יש פה סתירה - סימן ש-halt2 לא תעצור.
2. אבל אם halt2 לא תעצור, סימן ש-halt אמרה "כן" כששאלנו אותה האם halt2 תעצור על halt2. סימן ש-halt2
כן הייתה אמורה לעצור.
הגענו לכך שלא יכול להיות ש-halt2 עוצרת, ולא יכול להיות שהיא לא עוצרת. לכן יש פה סתירה.
מכאן שלא יכול להיות ש-halt המקורית קיימת בכלל.
זאת בגדול בעיית העצירה.
אני יודע שהמסר הוא שיש בעיות שלא ניתן לפתור ושלא צריך לבזבז את הזמן שלנו עליהם.
אני לא חושב שיש בזה מסר. או אולי אנשים בוחרים לקרוא בזה מסר. בסוף, זאת פשוט תופעה לוגית מעניינת, שממחישה שמחשב לא מסוגל לפתור כל בעיה שנותנים לו.
ג"נ מבזבז את הזמן שלי באופן סיסטמטי.
באופן כללי - זה דוגמא מצויינת לתהום בין תעשיה לאקדמיה.
באיזה מובן?
