בתשובה לאלון עמית, 11/06/05 3:55
(M=(Q,Σ,Γ,δ,q0,qa,qr 307920
אביב י. • בתשובה לאלון עמית שבת, 11/6/2005, 5:29
נ.ב.

בלי קשר לנושא התת-פתיל (המוח מול מ"ט), וסתם בגלל הסקרנות: איך פותרים טכנית את 2 ובאיזה מובן המודל שמתאר את הפיתרון הטכני נשאר מ"ט (ולא מודל אחר)? איך נראת קבוצת המצבים, הסרט או פונ' המעבר של מכונה כזאת, המתארת תהליכים חישוביים לא דיסקרטיים?
(M=(Q,Σ,Γ,δ,q0,qa,qr 308128
אלון עמית • בתשובה לאביב י. יום א', 12/6/2005, 8:42
ה"פתרון" שאני התכוונתי אליו הוא לא פתרון, אלא מעקף. העזתי להניח שמודל דיסקרטי מספיק צפוף יחקה מספיק טוב את המודל הרציף (אם יש באמת מודל רציף; אני לא חושב שסיכמנו שה"פיסיקה" היא באמת רציפה).

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

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

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

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

ועוד משהו: *יש* מודלים חישוביים עבור מספרים ממשיים; אני זוכר במעורפל ספר של Lovasz עם פרק על הנושא. אם זה מעניין אותך (או את גדי) אני יכול לחפש על זה חומר; כאמור, אני לא מאמין שזה באמת קשור לשאלת המוח.
(M=(Q,Σ,Γ,δ,q0,qa,qr 308134
אביב י. • בתשובה לאלון עמית יום א', 12/6/2005, 9:17
אויש נו :) זה יותר מעניין משאלת המוח.

תודה.
(M=(Q,Σ,Γ,δ,q0,qa,qr 308251
אביב י. • בתשובה לאלון עמית יום א', 12/6/2005, 19:34
רפרפתי בתוכן העניינים של כמה ספרים של Lovasz ולא מצאתי את הפרק הנ"ל. באיזה ספר הוא מופיע?
(M=(Q,Σ,Γ,δ,q0,qa,qr 308258
אלון עמית • בתשובה לאביב י. יום א', 12/6/2005, 19:52
גם אני טרם. אני אחפש.
(M=(Q,Σ,Γ,δ,q0,qa,qr 308447
אלון עמית • בתשובה לאביב י. יום ג', 14/6/2005, 2:13
*נדמה* לי שזה ב-
An Algorithmic Theory of Numbers, Graphs, and Convexity

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

<מחפש עוד קצת>

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

האמת, נראה ממש מעניין...
(M=(Q,Σ,Γ,δ,q0,qa,qr 309127
אביב י. • בתשובה לאלון עמית יום ה', 16/6/2005, 14:48
תודה רבה (ואפילו מצאתי את הספר בספריה!).
חזרה לעמוד הראשי
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות