שאלה מעניינת

[שייח ספיר]

תשובות:

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

 

[SilentMike]

אה.

תודה.

 

[vizini]

יש לך טעות יסודית.

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

 

[שייח ספיר]

???

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

 

[vizini]

!!!

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

 

[שייח ספיר]

כדי להבהיר את הנקודה שלי

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

 

[vizini]

אבל כל עוד אין לך אלגוריתם

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

 

[שייח ספיר]

אז מה אתה טוען?

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

 

[vizini]

אין שום בעיה. פשוט,

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

 

[שייח ספיר]

אני יכול לטעון מה שאני רוצה

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

 

[vizini]

הקופסא השחורה שלי, בדיוק כמו

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

 

[שייח ספיר]

לא נכון

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

 

[vizini]

האלגוריתם שלי יכשל בדיוק היכן

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

 

[vizini]

אגב, הנה אלגוריתם שלא יכשל בניסוי

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

 

[שייח ספיר]

בוודאי

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

 

[vizini]

מה זאת אומרת "הקופסא שלי לא

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

 

[שייח ספיר]

אוף

אתה חוזר פעם נוספת על אותה טעות. אז בוא ואחזור על השלבים לאט, אחד אחד: 1) נתונה קופסה שחורה ועליה שתי נורות A וB, כפתורים RESET וSTART וחיבור לקלט חיצוני, המקבלת כקלט זה אלגוריתמים (עם הקלט שלהם). התוצאה האפשרית אחרי שמועבר אלגוריתם הקלט ואחרי שלוחצים START היא אחת משלוש: * נורה A נדלקת. * נורה B נדלקת. * שום נורה לא נדלקת. 2) אני מציע תיאוריה (פנומנולוגית) לגבי הקופסה, המורכבת משתי טענות: * תמיד תדלק נורה לאחר זמן סופי. * נורה A תדלק תמיד כאשר האלגוריתם הנקלט עוצר על הקלט שלו, ונורה B תדלק תמיד כאשר האלגוריתם הנקלט איננו עוצר. 3) אתה מציע תיאוריה חלופית - בקופסה יש מחשב הפועל על פי אלגוריתם X, עם קצב פעולה מוגדר והוא המכתיב איזו נורה (אם בכלל) תדלק. 4) על מנת לבחון איזו תיאוריה תקפה, נחפש מקרים בהן הם נותנות ניבויים שונים. נבנה מאלגוריתם X אלגוריתם X' כך שמובטח שX' עם פלט X' לא יעצור, אבל אלגוריתם X יקבע תוך זמן T שהוא עוצר (זו בניה שתמיד ניתנת לביצוע). 5) נבחן את הקופסה השחורה במשך זמן T ונקבל הכרעה בין התיאוריות. 6) אם תיאוריית האלגוריתם X נכשלה אתה עשוי להציע תיאוריה חלופית עם אלגוריתם Y אשר איננה כושלת בX'. במקרה זה נבנה את Y' ובדוק את הקופסה במשך זמן T'. תיארתי כאן פרוצדורה מדעית שיטתית המאפשרת לקבוע אמפירית שהתיאוריה שהצעתי תקפה. כמובן, זו איננה "הוכחה", אבל לשום תיאוריה מדעית אין הוכחה. כל תיאוריה כזו היא אד-הוק.

 

[vizini]

לא, אתה חוזר פעם נוספת על אותה

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

 

[שייח ספיר]

התיאוריה החלופית שאתה מציע

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

 

[vizini]

זו לא הנקודה. הנקודה היא שהקופסא

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