שאלה מעניינת

[שייח ספיר]

לא

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

 

[vizini]

לא נכון.

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

 

[שייח ספיר]

דו שיח של חירשים

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

 

[vizini]

אולי.

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

 

[שייח ספיר]

נראה לי שפילוסופיית המדע שלך מוטעית

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

 

[vizini]

אנחנו לא מדברים פה על פילוסופיית

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

 

[שייח ספיר]

נסיון נוסף

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

 

[vizini]

ועדיין, ההצגה שלך סותרת

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

 

[שייח ספיר]

יש לך טעות

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

 

[vizini]

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

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

 

[שייח ספיר]

לא ולא

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

 

[vizini]

כן וכן. יש רק קופסא שחורה אחת,

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

 

[שייח ספיר]

עדיין לא

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

 

[SilentMike]

אבל אתה שוגה כאן בהנחה מוקדמת

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

 

[שייח ספיר]

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

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

 

[SilentMike]

פיסיקליות ולא לוגיות.

פיסיקליות ולא לוגיות כי היקום סופי ובדיד?

 

[vizini]

או.קי. אולי אי אפשר לסתור את

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

 

[Levos]

איני רואה מה ההבדל

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

 

[שייח ספיר]

יש הבדל גדול בין מערכת קוונטית

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

 

[SilentMike]

באיזה אופן לא ניתן לשכפל?

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