בתשובה לאלון עמית, 19/02/04 21:55
 |
|
 |
||
|
||||
 |
אם רוצים עוד פרטים טכניים או פילוסופיים על העניין הזה, רק צריך להצביע. |  |
 |
 |
|
|
|
||
|
||||
|
לרשויות המקומיות? <צליל תופי להקתו של ג'יי לנו> אם אתה יכול אז בכיף (אבל בלי יותר מדי פרטים טכניים, אם אפשר. יש דברים שאני אמור לדעת אבל ממש הייתי חולה באותו יום, באמת!). (אגב, יש גירסת חוקים ל-Life למערך תלת מימדי?) |
|
|
|
|
|
|
||
|
||||
|
לא, על דוגמה נגדית. <קווין יובנקס בריף על הבאס> בוא נגמור קודם עם Life במימד שלוש: אני לא בטוח מה השאלה בדיוק, כל אחד רשאי ומוזמן להמציא אילו חוקים שבא לו ולקרוא להם Universe, Life או Everything אם מתחשק לו. יש מי שטרח, אני חושב, למצוא חוקים המניבים תוצאות יפות, אבל יש בטח יותר מגרסה אחת כזו ואינני יודע אם אחת מהן דומה במיוחד למשחק המקורי. מהו חישוב, מהו אלגוריתם: אינטואיטיבית, אנו חושבים על "אלגוריתם" כעל מתכון מסודר לביצוע פעולות. מודל חישובי הוא איזשהו תיאור מדוייק של מה הם הצעדים היסודיים המותרים במתכון, ומה המבנה המדוייק של הקלט (מה שנכנס) והפלט (מה שיוצא). דוגמא: Mac המריץ תוכנה לחיזוי מזג האוויר. דוגמא פשוטה יותר: מכונת טיורינג. כאן יש רק סרט עליו אפשר לכתוב 0-ים ו-1-ים, ומין מנגנון שרוכב על הסרט ויודע רק לזוז צעד אחד ימינה או שמאלה ולכתוב 0 או 1, וזאת עפ"י מערכת כללים התלויה במה שרואה המנגנון מתחתיו כרגע (0 או 1) ומה "מצבו הפנימי", שהוא אחד מבין אוסף סופי וקבוע של מצבים. כלומר, כל הכללים נראים כמו: * אם אתה במצב 67 ורואה 0, כתוב 1, זוז צעד ימינה, ועבור למצב 163. (צריך גם לפחות כלל אחד שאומר "אם אתה במצב 131072 ורואה 1, עצור, די, גמרנו). בשביל מה זה טוב: זהו מודל פשוט מאוד שקל יחסית להשתמש בו כדי להוכיח טענות *על* מודלים חישוביים. יותר קל להוכיח שהצעצוע הזה לא יכול לעשות משהו מאשר לנסות להוכיח פורמלית שה-PC שלכם לא יכול לעשות אותו. אבל זה ממש צעצוע: אז זהו, שאפשר להראות שעם הצעצוע הזה ניתן לבצע כל מה שאפשר לבצע עם מחשב ביתי, או עם מכונת RAM, או עם מכונה בעלת אלף סרטים, או עם תכנות פונקציונלי, ובעצם כל מודל חישובי שמישהו הצליח אי-פעם לנסח (אני קצת מזניח חישוב אקראי וחישוב קוונטי, אפשר גם לזה להיכנס). אפשר, עקרונית, לבנות מכונת טיורינג שמשחקת שח בדיוק כמו Junior, או מתחזקת את "האייל הקורא" כולל מנוע חיפוש, או מריצה את תוכנת Mathematica (באמת יופי של כלי, אגב). מכונת טיורינג אוניברסלית: עקרונית מדובר על החלפה של החומרה של המנגנון בתוכנה. זוהי מכונת טיורינג *ספציפית*, עם מערכת *ספציפית* של כללי-התנהגות, שאפשר לבקש ממנה לעשות כל מה שמכונת טיורינג אחרת יודעת לעשות פשוט ע"י שרושמים על הסרט תיאור, בפורמט מסויים, של מכונת-הטיורינג ההיא. התיזה של Church-Turing: אם אפשר לחשב משהו, אפשר לחשב אותו ע"י מכונת טיורינג כלשהי (ולכן מכונת הטיורינג האוניברסלית הספציפית החביבה עלינו יכולה גם). למה שזה יהיה נכון: אי-אפשר "להוכיח" את זה, כי זו בעצם *הגדרה* של המושג "חישוב". אפשר רק להשתכנע ע"י שבודקים כל מיני מודלים חישוביים וכל מיני דוגמאות ספציפיות, כפי שהזכרנו. זו תיזה מאוד, מאוד, מאוד, מאוד, מאוד סבירה. ואיך זה קשור ל-Life: קונוויי התעניין במכונות טיורינג, ותהה כמה פשוטה יכולה להיות מכונת טיורינג אוניברסלית. ככל הידוע לי, הוא בנה את Life בתור תחליף פוטנציאלי פשוט למכונה כזו, ואח"כ הוא ואחרים השקיעו די הרבה מאמץ בניסיון להראות שאכן אפשר לסמלץ ב-Life מכונת טיורינג אוניברסלית. ככל הידוע לי, בסוף הצליחו. מה זה אומר: זה אומר שהרבה לפני וולפרם היו דוגמאות קונקרטיות למערכות בעלות כללים פשוטים מאוד היכולות לבצע מעללים מדהימים ומסובכים. ומה יש לאודי שפירא להגיד על זה: אודי שפירא, מדען במכון ויצמן, מנסה להראות (אולי כבר הצליח) שהריבוזומים בתא החי משוכללים מספיק כדי להיות מכונות טיורינג. הדמיון החזותי בין הראש הקורא של מכונת טיורינג לריבוזום הרוכב על הכרומוזום הוא אכן מרשים. על פילוסופיה, גבולות הידע האנושי, האם המוח הוא מכונת טיורינג ועוד, בפעם אחרת (כרגיל, אם יש ביקוש). |
|
|
|
|
|
|
||
|
||||
|
אפשר למצוא מכונות טיורינג במקומות *מאוד* מוזרים. קונווי חיפש את המודל הפשוט ביותר. צבי גוטרמן, בעבודת המאסטר שלו בטכניון, מצא, כך נדמה לי, את המקרה המסובך ביותר – או לפחות המופרע ביותר – המתועד: מסתבר שניתן לכתוב מכונת טיורינג בעזרת C++ templates, כך שהחישוב יתבצע על-ידי הקומפיילר *בזמן קומפילציה*, ולא בזמן ריצה. במילים אחרות, צבי הוכיח כי הידור של תוכנית cpp לא בהכרח יסתיים, ולא בשל בעיה במהדר אלא בשל אופייה של השפה. לטובת הספקנים שבקהל, הוא גם כתב תוכנית Perl שמייצרת תוכנית cpp מתאימה בהנתן הגדרה של מכונת טיורינג. |
|
|
|
|
|
|
||
|
||||
|
האו אמיוזינג... קשה, קשה להיות קומפיילר ++C. | |
|
|
|
|
|
||
|
||||
|
תודה על ההשקעה. אסיים לקרוא מחר (יש עVודה, יש לימודה, צריך משקיעות. קשה, קשה). ______ לגבי Life-3D - אני יודע שאפשר להמציא איזה משחק שרוצים. העניין הוא שעם כל הסימפטיה שיש לי למתמטיקה, אני ממש לא מתמטיקאי ברוחי ואינני מתכוון להשקיע את זמני בענייני איזומורפיזם. אותי מעניין דווקא יותר השעשוע הויזואלי שבתכנות ובמשחק עם אלגוריתמים. לכן, התכוונתי לשאול בעצם אם יש משהו מוגדר וידוע בתלת מימד שגם נחמד לשחק איתו וגם יש בו כל מיני תופעות נחמדות כמו ה"גליידרים" וכו' (אני יודע, "נחמד" זו לא הגדרה מדויקת, אבל בכל זאת). אני פשוט משתעשע בזמן האחרון עם תכנות ב-DirectX וחשבתי שזה יהיה תירגול חביב. מחר אציק קצת לאדון גוגל במקום להטריד איילים חפים מפשע. |
|
|
|
|
|
|
||
|
||||
|
הבנתי מה זה מכונת טיורינג או אלגוריתם. מה שלי לא ברור עדיין זה ההגדרה של "משוואה מתימטית" ושונותה המהותי מאלגוריתם. בהנחה שמדובר על אוסף סמלים מוגדרים הנמצאים משני צידי המתרס של הסימן "=", האם לא ניתן בצורה כלשהי להפוך כל אלגוריתם למשוואה? (אף אם במחיר של פשטות). אם יש דרך לעשות זאת, אז אני מבין שהוויכוח הוא בעיקר על טיב המתודולוגיה לתיאור התופעות, כאשר פשטות (או אקונומיות) ההצגה נכנס כקריטריון מהותי. (עכשיו כשאני חושב על זה, אני מניח שכמות הביטים להצגה משפיעה באופן ישיר על החישוביות הכללית, אבל אשמח אם תרחיב על כך...) ואם כבר הזכרתי פשטות/אקונומיות/אלגנטיות - האם לזאת הכוונה במונח החופשי משהו "יופי" או שהמילה "יופי" לתיאוריות מתימטיות מדברת על משהו אחר (נניח סקר דעת קהל בקרב מתימטיקאים :-))? |
|
|
|
|
|
|
||
|
||||
|
בגדול, אני חושב שהתשובה היא "לא". קח את האלגוריתם האוקלידי, למשל. לא ברור לי איך אפשר להפוך אותו למשוואה. כשהאלגוריתם עוסק במבני נתונים יותר מורכבים, עוד פחות ברור איך משוואה צריכה להיראות או מה היא צריכה לייצג. את מיון מהיר תייצג באמצעות איזו משוואה? יש גם אלגוריתמים שאני פחות בטוח בקשר אליהם, נניח הקירוב של ניוטון: שם יש לך משוואה רקורסיבית, אז כן יש משוואה כלשהי, ומצד שני אין דרך לפתור את הכל בבת אחת, זה חייב להיות תהליך בשלבים. בסך הכל אלגוריתם הוא *שיטה*, וככזה יש לו הרבה יותר כוח מאשר משוואה אחת. כל האלגוריתמים שהצגתי כאן הם פשוטים מאוד. גם אם האלגוריתם שלך נותן תוצאה מספרית פשוטה, החישוב שלה עשוי להיות מאוד מסובך, ומשוואה לא תיתן את המידע הדרוש עבורו - לא לכל נוסחאות הנסיגה יש פתרון כללי, אז לכל אלגוריתם? |
|
|
|
|
|
|
||
|
||||
|
גם אני לא מומחה. לכן שאלתי מה ההגדרה ל"משוואה מתימטית" - האם למשל קבוצה של משוואות מתימטיות המגדירות יחדיו בעיה מסויימת זה "משוואה מתימטית"? (כלומר, האם מותר לנו להשתמש בכמתים לוגיים?) בהתייחס לדוגמאות שנתת: לגבי הדוגמא הראשונה, ניתן להציג את הבעיה כך: b בצעד ה i+1 שווה ל-a בצעד ה-i מודולו b בצעד ה-i a בצעד ה- i+1 שווה ל- b בצעד ה-i האם זהו תיאור נכון של הבעיה, ואם כן האם זהו תיאור משוואתי, אלגוריתמי או שניהם? לגבי הדוגמה השניה, עד כמה שאני יודע כאן כבר מדובר באלגוריתם רנדומי, משהו שעוד לא דנו בו כאן עדיין. ספציפית לגבי אלגוריתם זה הוא אמנם מסוג לאס-וגאס, כלומר נותן בסוף פתרון נכון לבעיה, אבל יש גם אלגוריתמים מסוג מונטה-קארלו שלא מחוייבים כלל להגיע לפתרון - לכן נדמה לי שכאן הסיפור כבר יותר מורכב, ואני כלל לא בטוח אם השאלה שלי לגבי הקשר בין משוואות לאלגוריתמים תקפה כאן ללא מגבלות נוספות. |
|
|
|
|
|
|
||
|
||||
|
התרגום שלך בסדר, אבל הוא עשוי להסתבך אם האלגוריתם יכיל, למשל, פיצולים (if statements). בכל אופן אני לא בטוח שיש משמעות אמיתית לשאלה האם זהו תאור משוואתי או אלגוריתמי. אינני סבור שיש הגדרה מדוייקת של "מהי מערכת משוואות" האוסרת או מתירה כמתים. | |
|
|
|
|
|
||
|
||||
|
ההגדרה של ערך מוחלט, שמטבעה יש בה פיצול, היא לא דוגמא להכנסת תנאים, ולו בעקיפין, אל תוך משוואות? המשוואה x=abs(x) בעצם אומרת "אם איקס חיובי, אל תעשה כלום. אם איקס שלילי, הכפל אותו במינוס 1". | |
|
|
|
|
|
||
|
||||
|
נכון, אז...? יש שיטות מקובלות לחלק למקרים בהגדרה של פונקציה, וודאי שאפשר לרשום משוואות שונות לכל מיני מצבים. רק ציינתי שאם תתאמץ להפוך אלגוריתם עתיר פיצולים למערכת משוואות תגיע במהירות למצב שבו המשוואות תהיינה הרבה פחות שימושיות או מאירות-עיניים מהתיאור האלגוריתמי. אני לא חושב שהדיון הוא דיון תאורטי על האפשרות להפוך כל אלגוריתם למערכת משוואות (אבל אולי לא הבנתי על מה הדיון). במקרה הכי גרוע אפשר לממש מכונת טיורינג עם גלגילות ומנופים ולרשום את משוואות התנועה הקלאסיות של המערכת. אבל למה שנעשה זאת? בשביל להיווכח שוולפרם לא מציע באמת פרדיגמה חדשה, זה אוברקיל רציני. |
|
|
|
|
|
|
||
|
||||
|
סוף סוף הזדמנות לשאול - מה עושה ה"מודולו" הזה? בתודה מראש. |
|
|
|
|
|
|
||
|
||||
|
a mod b=c אם ורק אם a=nb+c כש-n מספר שלם. במילים פשוטות: השארית שמתקבלת מחלוקת a ב-b. יש גם "מחלקות שקילות" מודולו n כלשהו. הדבר הזה הוא קבוצת כל קבוצות המספרים שנותנים אותה שארית כשמחלקים אותם ב-n. למשל, כשאנחנו עובדים עם n=2 יש לנו שתי מחלקות שכאלו: כל המספרים הזוגיים (שנותנים שארית 0) וכל האי-זוגיים (שנותנים שארית 1). |
|
|
|
|
|
|
||
|
||||
|
a מודולו b או a%b עונה לנוסחה הבאה: a%b = a - floor(a/b) * b או במילים אחרות זאת השארית לאחר שמחלקים את a ב- b floor - עיגול השבר שמתקבל לשלם הכי קרוב אליו מלמטה. דוגמה פשוטה: 7%4. החלוקה נותנת 1.75, אז מעגלים למטה ל - 1 ומכפילים ב- 4. את התוצאה (4) מחסרים מ - 7 ומקבלים את השארית 3. המתימטיקאים שבאתר מוזמנים כמובן לתקן אילו אי-דיוקים שכתבתי כאן. % = מודולו, ולמעשה נאבקתי כחצי שעה בנסיון לכתוב את הדברים בתגובה הקודמת עם סבסקריפטים וסימבולים כמו שצריך (במקום תיאור מילולי של משוואות), אך לא מצאתי כל דרך להעתיק לפה משוואות מ- Word. |
|
|
|
|
|
|
||
|
||||
|
בעצם כנראה % מקובל רק במחשבים, ובטח רק בשפה מסויימת... 'צטערת | |
|
|
|
|
|
||
|
||||
|
למשל, המינימום במספרים חיוביים של הביטוי ax+by (כשמציבים במקום x ו-y מספרים שלמים) ייתן לך את המחלק המשותף המקסימלי בינהם. למה הכוונה בלהפוך אלגוריתם למשוואה? שהפיתרון שלה יהיה ערך המטרה של האלגוריתם, או שאתה רוצה שיהיה שם גם ייצוג לאופן פעולת האלגוריתם? |
|
|
|
|
|
|
||
|
||||
|
ערך המטרה. אבל כשאתה בונה משוואה, היא צריכה להצביע גם על דרך החישוב. אבל אני מודה שאני לא מבין בזה מספיק וקל לראות איך זה מתערפל: חישוב של מינימום יכול להיות בעייתי, וכשמגיעים לאינטגרלים, שממש מככבים במשוואות, חישוב שלהם יכול להיות סיוט של ממש. אז מוטב שאודה כבר עכשיו שאני לא ממש יכול לומר בודאות למה אני מתכוון. | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שאני מצליח למצוא פרשנות מתאימה לשאלה. משוואה, כפי שציינת, מתארת שוויון בין שני אובייקטים (מספרים, פונקציות, או משהו אחר), ואלגוריתם הוא תיאור של תהליך מסודר לביצוע פעולות; אינני בטוח שיש מובן סביר לתהליך ההמרה של אלגוריתם למשוואה. משוואות לעיתים מתארות "שמורות" של מערכת פיסיקלית, וכשיש אלגוריתם אפשר לחפש את השמורות של המערכת ואם מוצאים מספיק כאלה אז אולי אפשר להחליף את האלגוריתם במשוואות, אבל זה לא בהכרח תמיד המצב. זה שיש מתודולוגיות שונות לתאר תופעות זה נכון, אבל אני אישית לא מסכים עם וולפרם שיש פה איזה ויכוח עמוק. מסתכלים על העולם ומנסים למצוא לו תיאור מעניין או שימושי, ובמקרים רבים הכלים הנוחים לעשות זאת הם משוואות המתארות "חוקים" מסויימים, אך בהחלט לא תמיד. עקרון הפעולה המינימלית, למשל, הוא לא "משוואה", אלא עקרון המסביר כיצד מערכת פיסיקלית תבחר להתנהג. מתמטיקה היא לא רק משוואות, ופיסיקאים בשנים האחרונות מצאו עצמם (לשמחתם של חלק, לצערם של אחרים) משתמשים באובייקטים מתמטיים לא-צפויים עד מאוד. הבדל אחד, לא מהותי אבל קיים מסורתית, בין תאורים אלגוריתמיים למשוואות הוא הפער בין הדיסקרטי לרציף. אלגוריתמים נוטים לפעול באופן דיסקרטי צעד אחר צעד, ומשוואות (נגיד דיפרנציאליות) נוטות לתאר אלמנטים רציפים בזמן רציף, אך אין בעייה לבנות משוואות גם למערכות דיסקרטיות. פשטות ההצגה הוא באמת פרמטר שנראה, אינטואיטיבית, חשוב. אם תהייה תורה שלמה של העולם הבנוייה על שבעה כוחות, שש-עשרה משוואות שדה שונות, וחמישים פרמטרים שרירותיים (כמו מסת האלקטרון, המומנט המגנטי של המיואון, וכאלה), אני מניח שפיסיקאים ימשיכו לחפש אחר תורה שקולה מבחינת ניבויים אבל חסכונית יותר מבחינת נפח ההצגה. אין, כמובן, שום ערבות שהעולם בנוי על כללים פשוטים, אבל הדחף לחפש כאלה, דומני, טבוע בנו עוד מאז שהקדמונים ניסו לחלק את כל עולם החומר לאדמה, רוח, מים ואש. כמות הביטים הדרושים כדי לנסח תאוריה (בתוך מודל נתון של חישוב) הוא בהחלט מדד סביר לסיבוכיות או לפשטות שלה. אינני בטוח שאני מבין למה הכוונה בהשפעה על "החישוביות הכללית"; ייתכנו כללים מסובכים ומסורבלים שקל מאוד לחשב בעזרתם את עתיד המערכת, וייתכנו כללים פשוטים מאוד שלא יאפשרו לעשות זאת בקלות. אני חושב שפשטות התיאור חשובה יותר מקלות החישוב. מושג ה"יופי" הוא כמובן לא משהו שיש לו איזה ניסוח מתמטי, ונראה לי שאקונומיות גרידא אינה מספיקה כדי להפוך תאוריה מתמטית ליפה (ההגדרה של חבורה-למחצה יותר קצרה מההגדרה של חבורה, אך התורה המתמטית השנייה עשירה ויפה בהרבה). אני לא יודע אם עזרתי, כל זה נראה לי קצת מופשט. |
|
|
|
|
|
|
||
|
||||
|
אני מסכים איתך שזה קצת מופשט, ואולי מטה-מתימטי ולא מתימטי, אבל זה נראה לי חשוב בהקשר של הכתבה שמשתמשת במונחים שלגביהם אני תוהה. ובהחלט עזרת, שכן הראית לי ששאלותיי (הבאות מרקע לא מספיק מתימטי) לא לגמרי מטומטמות ושיש טעם (לדעתי... :-)) לדון במושגים המתימטיים השונים (בניגוד להארדי אני לא מתימטיקאי, כך שאני יכול להרשות לעצמי לעשות זאת מבלי להתנצל...). לגבי עצם הדברים: - העלית בתשובתך קשר בין מתימטיקה לבין פיסיקה שמאוד מעניין אותי כסוגיה בפני עצמה. האם לדעתך האישית המתימטיקה אומרת משהו על העולם (כלומר, כמו שראסל האמין בעקבות קאנט, יש בה אלמנט סינתטי) או שיש היום תמימות דיעים מוחלטת בקרב המתימטיקאים לגבי אופיה האנליטי לגמרי? במילים אחרות, האם זו בסך הכל שפה סימבולית וכללי גזירה, או שיש קישור אמיתי לעולם (אני מודע לניסוח הבעייתי ולכן מנסה כמה); קשר לעולם, דרך-אגב יכול להתבטא בכמה מישורים: (1) הסמלים מצביעים לישים בעולם. (2) דרך מבנה עומק או כל ניסוח אחר שאינו בהכרח מריח מחומסקי אך מדבר על מבנה (לוגי או אחר) כלשהו שקיים בעולם וממופה לכזה הקיים במתימטיקה. - מעניין אותי גם הקשר בין הדיסקרטי לרציף, ונראה לי שזה מתקשר לנקודה הראשונה שאני מעלה. יש מטאפיסיקאים/פיסיקאים/פילוסופים שהאמינו בקונטיניאום של היקום/חשיבה (למשל פירס) לעומת כאלה שחשבו שהיקום דיסקרטי (אולי קארנאפ? אני לא בטוח) - ייתכן אם כן שיש לכך חשיבות או השפעה על סוג המתימטיקה שיותר שימושי, בהתאם למה התמונה האמיתית של העולם... אבל ייתכן גם שאני מגבב שטויות... - לגבי פשטות הצגה: אם ישנן שתי תיאוריות זהות לגמרי אחורנית וניבואית מלבד אלמנט הפשטות (נניח תורת היחסות לבדה, לעומת שילוב בין תורת ניוטון (נניח רק למהירויות קטנות יחסית) עם תורת היחסות (למהירויות גדולות מספיק) - הקרדיט על ניסוי מחשבתי זה נתון למישהו בשם "אודי אהרוני" ממנו שמעתי זאת. ברור כי התיאוריה הראשונה פשוטה יותר מהשניה, אף כי שתיהן גם עונות על העובדות הקיימות וגם מנבאות בדיוק אותו דבר), האם תיבחר התיאוריה הפשוטה יותר כי היא יותר יפה? או האם היא תיבחר בגלל שנניח יש קשר בין כמות הביטים הנדרשת להצגה לבין מאמץ הבדיקה, כמות הבאגים האפשרית וכדומה, כלומר, על-שום שיש יתרון אמיתי אינטרינזי/שימושי כלשהו לפשטות. אתה ניסית לקשר את מושג היופי בהקשר המתימטי לעושר - אולי, אם כן, יש איזשהו יחס בין אקונומיות ההצגה של תיאוריה לבין העושר שלה (כלומר, עושר תורת החבורות הוא גדול יותר ביחס לסיבוכיות הייצוג שלה יותר מאשר אותו יחס בחבורות למחצה). - לגבי סיבוכיות ייצוגית. אני מניח שניסיתי להפריד אותה מסיבוכיות ריצה. מצד שני, לא ברור לי איך מגדירים "סיבוכיות ריצה" למשהו סטאטי כמו משוואות. זהו. אני מקווה שלא תמצא את הגיגיי משעממים מידי, וגם תשובות למחצה ייתקבלו בברכה, שהרי לשם כך קיים הדיון/חקירה. |
|
|
|
|
|
|
||
|
||||
|
רק לדייק - המתמטיקה לא אומרת שום דבר על העולם. מה שמוזר הוא שהעולם מתנהג בצורה הנתנת לנתוח "מוצלח" בכלים מתמטיים, כמו צורות גאומטריות אידאליות ומשוואות דיפרנציאליות. זו תצפית אמפירית על היקום כמו שאנו חווים אותו. ניתן בקלות לחשוב על עולם שבו עובדה זו לא מתקיימת - דמיין את גלילאו משליך אבנים מהמגדל רק כדי לגלות שהן מתנהגות באופן אקראי לגמרי (כנראה שבעולם כזה לא היה ניתן לבנות מגדל, אבל לא משנה...) אני לא יודע מה המשמעות האמיתית של התצפית הזו. האם היא מספרת לנו על מגבלות התפיסה האנושית? אולי על רציונליות מובנית ביקום? על (אי) קיומה של ישות "אלוהית"? אני באמת לא יודע וזה קצת כבד בשביל שבת בבוקר. |
|
|
|
|
|
|
||
|
||||
|
אני לא בטוח שאני מסכים... נראה לי שהטענות המתמטיות הבאות דווקא אומרות משהו על העולם: 1. בכל קבוצה של 18 אנשים יש ארבעה שמכירים זה את זה או ארבעה זרים. 2. 32^1+2 איננו מספר ראשוני. 3. אין מכונת טיורינג הפותרת את בעיית העצירה. נכון שהרלוונטיות ל"פיסיקה", במובן המקובל, היא אולי מקרית - אבל זה מקרה מפתיע מאוד, כפי שציינת. |
|
|
|
|
|
|
||
|
||||
|
מתמטיקה היא מדע? (כותרת התגובה הראשונה בפתיל הרוולנטי: "מתמטיקה היא לא מדע"). |
|
|
|
|
|
|
||
|
||||
|
לא יודע איך להשיב על השאלה הזו1, ו... למה זה קשור למה שאמרתי? בכל אופן, במקום שנתחיל להתווכח(?), אולי פשוט נקרא את הפתיל ההוא ונתווכח בלב עם המתדיינים: תגובה 136505. 1 היא נראית לי מסוג השאלות שאם הן ברורות (דהיינו, ברור לך מהו מדע ואתה מנסה להבין אם מתמטיקה היא כזו), אז הן פשוטות וקלות, ואם הן נושא לדיון, אז כנראה שהן לא מאוד ברורות (הדיון הוא על גבולות המושג "מדע"). |
|
|
|
|
|
|
||
|
||||
|
אני לא יודע אם קראת את הארדי (כדאי מאוד), אבל הוא ממש לא מתנצל :-) השאלה הראשונה ששאלת היא מעניינת מאוד, ותכף נגיע אליה, אך היא שונה קצת ממה שבד"כ נדון תחת הכותרת שנתת לה, "הקשר שבין מתמטיקה לפיסיקה", שהיא שאלה מעניינת אחרת: ההצלחה המפליאה של מושגים מתמטיים בתאוריות הפיסיקליות, בפרט המודרניות. זו לא עובדה טריויאלית כפי שאולי נדמה מכך שחלק ניכר מהמתמטיקה פותח על-מנת לתאר תופעות פיסיקליות. אולי נדבר גם על זה אח"כ. השאלות שכן שאלת נוגעות לחלק ממה שקרוי הפילוסופיה של המתמטיקה, ספציפית לזיקה (אם יש כזו) בין המבנים המתמטיים ל"עולם האמיתי". האם המספרים הטבעיים קיימים? והממשיים? ומושג האינסוף? האם, כפי ששאלת, מתמטיקה היא מניפולציה סינטקטית של סימנים, או שהיא מסמלת באיזה אופן את העולם? אינני סבור שיש היום תמימות-דעים בקרב המתמטיקאים (או הפילוסופים) בקשר לשאלות אלו, אך המצב היום נראה גם יותר ברור וגם יותר מורכב מכפי שהיה בעשורים הראשונים של המאה העשרים. אפשר לכתוב מאמר ארוך על הנושא הזה; בינתיים אזרוק כמה הערות כלליות. לגישה האקסיומטית הפורמלית יש מקום מרכזי מאוד במתמטיקה, אך סבורני שיש מעט אנשים יחסית המניחים שמתמטיקה היא פורמליזם מכני ותו-לא; אחרי הכל, אנחנו מאמינים שכשאנחנו מדברים על המספרים הטבעיים, אנחנו מדברים על משהו "אמיתי" ש"נמצא שם", ולעומת זאת אנו יודעים פחות או יותר ששום מערכת פורמלית איננה יכולה לתת תשובות מלאות על מספרים אלה. אני אנסה להסביר: ישנן מערכות פורמליות פשוטות (אקסיומות פאנו מסדר ראשון, נניח) המאפשרות לדון במספרים הטבעיים ולהוכיח תכונות מסויימות שלהם, אך אנו יודעים שמערכת כזו, אם אין בה סתירות, תמיד תהיינה בה טענות אותן לא ניתן להוכיח. קצת על הנושא הזה יש בפתיל הארוך מתחת לתגובה 164351, ושים לב גם לתגובה 171334 הסוגרת איזה ויכוח קצר שהתעורר שם (וסליחה שאני שוב שולח אותך לפתיל מייגע תחת המאמר ההוא). במילים אחרות, מערכות אקסיומטיות במתמטיקה נוצרות במקרים רבים מתוך ניסיון לתאר בצורה מדוייקת איזושהי ישות אינטואיטיבית (או לא כל כך אינטואיטיבית) - המישור האוקלידי, המספרים הטבעיים, מבנים אלגבריים שונים וכו', אך אנו מבינים כיום שבמקרים מורכבים מספיק לא ניתן יהיה לתת תיאור פורמלי שלם וחד-משמעי של הדבר אותו אנו מנסים למדל (גיאומטריה של המישור היא דווקא דוגמה למערכת בה הבעייה הזו לא מתעוררת). אפשר להרחיב, למשל, לגבי המצב המסתורי של השערת-הרצף, והיחס של מתמטיקאים שונים למטא-שאלה, "האם יש משמעות לשאלה אם השערת הרצף נכונה או לא". הקשרים בין הרציף והדיסקרטי במתמטיקה הם חשובים ועמוקים, אבל אינני בטוח שיש קשר הכרחי בין השאלה אם היקום באמת רציף או דיסקרטי לשאלת הישימות של מתמטיקה דיסקרטית או רציפה לתיאור העולם. הסיבה היא פשוטה: גם בתוך המתמטיקה יש שלל מצבים בהן הדרך הנוחה ללמוד ישויות דיסקרטיות היא דווקא באמצעות מושגים רציפים - ולהיפך. לשאלת הבחירה בין תאוריות זהות מבחינה ניבויית: אני אישית מאמין שהסיבות לבחור בפשוטה יותר הן אסתטיות גרידא, ולא נובעות משיקולים של שימושיות או מיעוט-באגים או איזה יתרון "אינטרינזי" אחר. מדד ה"יחס" בין עושר התורה לסיבוכיות הניסוח שלה נשמע לי נחמד, אך חשוב להדגיש שאין כמובן דרך אמיתית לכמת את העושר המתקבל, ועל מושג היופי משפיעים עוד הרבה גורמים השונים מאדם לאדם. את עניין הסיבוכיות לא בטוח שהבנתי... איך הגענו לזה? ולבסוף, אם תצליח לשעמם אותי עם הגיגים מתמטיים, תגיע לך מדליה. |
|
|
|
|
|
|
||
|
||||
|
איך, לכל הרוחות, בחרת דווקא ב"המומנט המגנטי של המיואון"? פיזיקאים: זה המקום לתת את ההערכה שלכם אם זאת אנומליה אמיתית או שזאת תנודה סטטיסטית שתיעלם עם הזמן (אבל סיגמא 4.2 זה לא משהו שנתקלים בו כל יום). כהדיוט אני מוכן לתת ניחוש משלי: לא יהיה כלום כי אין כלום. |
|
|
|
|
|
|
||
|
||||
|
אני חושש שההערכה שלך נכונה, אבל מקווה שאולי דוקא לא - שאחרת המאיץ היקר והמפלצתי הזה כבר 15 שנה יוצר פחות תוכן מקורי מנטפליקס: את הכל כבר ראינו וכל הטוויסטים נדושים וצפויים למרחוק. | |
|
|
|
|
|
||
|
||||
|
התוצאה היא מפרמי-לב, לא מה-LHC. אבל גם בצרן יש אינדקציה לחדשות. (לגבי המואונים, יחד עם פרסום תוצאות המדידות, התפרסם מאמר בנייצ'ר לפיו לא מדובר בכלל בסטייה - אלא בתוצאה החזויה לפי המודל הסטנדרטי - והחישוב התאורטי הקודם שגוי. אז ייתכן גם שהסטייה אמיתית לגמרי, אבל אין בה שום חידוש). |
|
|
|
|
|
|
||
|
||||
|
אם התוצאה אמיתית האם זה יפטור אותנו מעונשה של QCD? [אימוג'י של תפילה] | |
|
|
|
|
|
||
|
||||
|
האם תוכל להסביר לי בשפה פשוטה למה היפותזת צ'רצ'-טיורינג כ"כ כ"כ סבירה? מה יש במערכת הבסיסית הזו שמגדיר *בדיוק* את כל מה שצריך כדי לממש כל אלגוריתם? ועוד לגבי ההיפותזה הבסיסית והמסתורית הזו (בעיני), מה הקשר בין מה שנחשב פתיר ולא פתיר אלגוריתמית למה שנחשב ניתן להוכחה אם לאו במתמטיקה (עפ"י גדל)? כמו כן, למיטב ידיעתי העבודה של אודי שפירו על "מחשבים ביולוגים" אינה מבוססת על ריבוזומים (המייצרים פלט חלבונים מקלט של RNA) אלא על ה-DNA לבדו. (אבל אולי אני כבר לא מעודכן) |
|
|
|
|
|
|
||
|
||||
|
קודם כל אבהיר שאינני טוען שההיפותזה נראית סבירה *במבט ראשון* - נהפוך הוא, במבט ראשון מכונת-טיורינג נראית משהו פרימיטיבי עד-מאוד. התיזה הופכת לסבירה בשני תנאים: אחד, שמבהירים מה היא בעצם טוענת ומה הם גבולות היומרה שלה, ושניים, שמראים פורמלית (וזו עבודה) שבעזרת מכונת-טיורינג אפשר לבצע כמה וכמה פעולות יותר "גבוהות", שמהן כבר פחות קשה להאמין שאפשר הכל. קודם כל ננסה לחדד את מהות התיזה. מדובר בחישוב - כלומר, תהליך שמתחיל מנתונים מסויימים, טוחן טוחן טוחן, ומניב תוצאה. מניחים שהחישוב הוא דטרמיניסטי1, כלומר שמי שמחשב יודע בכל רגע נתון מה עליו לעשות, והוא לא מנחש או נועץ בכוכבים או מתבלבל. הנתונים, הקלט והפלט, הם או מספרים טבעיים, או רצפים סופיים של אותיות מא"ב סופי מסויים (למשל רצפים של סיביות) - אין זה משנה כי קל לתרגם מהאחד לשני. הנתונים אינם יכולים להיות, נניח, מספרים ממשיים (הדורשים אינסוף מידע כדי לייצגם2). מדוע שנניח שכל "חישוב" עוסק ברצפים סופיים של סמלים? ההנחה הממשית היחידה פה היא סופיות, והיא נראית סבירה: אם צריך אינסוף זמן רק כדי לקרוא את השאלה, קשה לראות איזו משמעות יש לחישוב. "רצף סופי של סמלים" הוא מושג גמיש מספיק כדי לאפשר לאלגוריתם לטפל גם בתמונות (סרוקות), במוסיקה (דגומה), באובייקטים מתמטיים (שיש להם תיאור סופי), וכו'. במילים אחרות, לומר שחישוב הוא תהליך שמקבל מחרוזת של אותיות, ומוציא איזו מחרוזת אחרת, זהו תיאור גמיש מספיק כדי לכלול (נגיד) בדיקת ראשוניות של מספר, מיקסוס של ערוצי שמע, חיפוש גנים בדנ"א, תכנון של צ'יפ, חיפוש ב"אייל", דחיסת תמונה, ועוד כהנה וכהנה. עכשיו, מה אתה עושה כשאתה "מחשב" משהו מקלט שהוא רצף של אותיות? אתה מבצע פעולות אריתמטיות פשוטות, אתה זוכר תוצאות ביניים, אתה מקבל החלטות על-סמך תוצאות קודמות, אתה מוחק ומשנה דברים שרשמת קודם, ובערך זהו. אם חסר לך משהו בתיאור הפשטני הזה, תאמר ונראה אם אפשר להוסיף אותו. את התיאור הזה קל יחסית לפרמל ע"י, נניח, שפת התכנות החביבה עליך בסביבה של מחשב עם זיכרון גישה אקראי. נשמע סביר? לבסוף, צריך להראות שמכונת הטיורינג האומללה מסוגלת לבצע את כל מה שנדרש משפת התכנות ההיא. זה קצת מייגע אבל לא נורא מסובך - אם *זה* מה שמציק לך בתיזה של צ'רץ'-טיורינג, וכל הלהג עד כה היה מיותר, תגיד וניכנס גם לזה. -- על הקשר בין מה שפתיר ולא פתיר אלגוריתמית למה שניתן להוכיח במערכת פורמלית אני אכתוב בנפרד, אחרת ההודעה תתארך עד מאוד (כאילו שהיא לא ארוכה כבר). בקשר לאודי שפירו (אתה צודק, משום מה זכרתי שהוא כותב "שפירא"), אנחנו מדברים על עבודות שונות - חישוב באמצעות דנ"א הוא נושא חמוד כשלעצמו ואף בוצע מעשית (לא זוכר אם גם ע"י אודי עצמו), אבל אני מדבר על עבודה שככל הידוע לי נותרה תיאורטית ובה הוא מנסה לראות אם לריבוזום יש גמישות פונקציונלית מספקת כדי לתפקד כמכונת-טיורינג. שמעתי על זה הרצאה ממנו, אינני יודע כמה הוא המשיך להתעמק בזה ומה, אם בכלל, פורסם. 1 לאוטומטים לא דטרמיניסטיים יש שימושים תיאורטיים חשובים, כמו בהגדרת המחלקה NP, אך בהקשר הנוכחי סביר לדרוש מ"חישוב" או "אלגוריתם" להיות חד-משמעי ולא תלוי בניחושים. 2 יש מודלים אחרים של חישוב הדנים בממשיים, אך זה סיפור אחר. |
|
|
|
|
|
|
||
|
||||
|
תודה. ענית לי אבל גם לא. בסדר, אז ניתן לסמלץ פתרון בעיות *מאד* מסובכות על מכונת טיורינג. ניתן אפילו למכור במילים את היכולת של מכונה כזו לקרוא קלט סופי (הסרט עליה יושב "הראש" דווקא אינסופי למיטב ידיעתי) ולכתוב מסקנות ביניים. אפילו להוכיח שוויון של המכונה לשפות התכנות המוכרות והאהובות הינה משימה אפשרית לדברייך. אבל מאיפה העוז לקבוע ש*כל* אלגוריתם ניתן להרצה ע"י מכונה זו, או אם להיות יותר סנסציוני, שכל מה שלא ניתן להרצה על מכונת טיורינג לא ניתן להרצה על שום חומרה אחרת? מה אתה יכול לספר על רעיון הריבוזומים הזה? תן אותה ב-גֶדֵל : ) |
|
|
|
|
|
|
||
|
||||
|
זה כמובן תלוי באיך אתה מגדיר *אלגוריתם*. כל הגדרה סבירה תהיה משהוא בסגנון הבא: מכונה המאפשרת לחשב את הערך (=פלט) של פונקציה מתמטית מסויימת, על קלט X כלשהוא, באמצעות הפעלת סדרת פעולות לפי סט כללים קבוע וסופי (מסובך ככל שיהיה). מן הסתם אתה תרשה לאלג' להשתמש בזיכרון (אולי אפילו אינסופי). זה בדיוק מה שמכונת טורינג מאפשרת1 (היא אפילו לא מחייבת שהאלג' יסתיים בזמן סופי). כל מודל הגיוני אחר הם רדוקטיבי ל-TM באופן טריביאלי *מאוד*. לא נראה שיש איזשהוא מודל הגיוני (כלומר כזה שהפלט שלו מוגדר היטב) שמאפשר הרצה של יותר אלגוריתמים. אתה מוזמן לחפש מודל כזה. אולי כדאי לציין כקוריוז שיש המון פונ' מתמטיות שלא ניתן לבנות עבורן אלג' (ב-TM), למעשה הרבה יותר מאשר כאלו שכן ניתן לבנות להן אלג'. אין שום קשר לגדל אלא אם כן אתה משתמש במונח זה כבמעין "אווה מריה". 1 תחת ההנחות שציין אלון. וניתן להסיר אותן במאמץ קטן. |
|
|
|
|
|
|
||
|
||||
|
תוכל לתת כמה דוגמאות של הפונקציות הללו, או שרק הוכח הקיום שלהן אבל לא מצאו דוגמא? (אני חושב שאני זוכר במעורפל ששמעתי משהו על שימוש במשפט קנטור על קבוצת השפות הפורמליות או משהו בסגנון. צריך ללמוד את זה באמת) | |
|
|
|
|
|
||
|
||||
|
המינוח המדוייק שצריך להשתמש בו הוא שפות בלתי כריעות (השתמשתי במונח פונקציות רק לצורך הבהרה). מצאו כמה כאלו, אבל הדוגמא היחידה שאני זוכר זו בעית העצירה1. הקיום של הרבה שפות בלתי כריעות כאלו נובע בפשטות מכך שיש הרבה יותר שפות (שתיים בחזקת ALEF EFES) מאשר אלגוריתמים (ALEF EFES). _________ 1 בהינתן מכונת טורינג M וקלט מסויים עבורה X, החלט האם M תסיים את ריצתה על X בזמן סופי או לא (בשפת העם, תיכנס ללולאה אינסופית). |
|
|
|
|
|
|
||
|
||||
|
קצת מוזר שמכל הטקסט הזה, את שתי המלים הכי-עבריות החלטת לשעתק: ALEF זה אלף, EFES זה אפס. | |
|
|
|
|
|
||
|
||||
|
ראה, למשל: |
|
|
|
|
|
|
||
|
||||
|
תודה. הנושא של fair non-determinism נשמע מעניין מאוד. שאר המודלים האלטרנטיביים מסתמכים באופן "כבד" על איזשהוא משאב אינסופי, ואז זה לא מאוד מפתיע שיש להם יותר כח (אני מקווה שלא יסתבר שגם ה-fair non-determinism מסתמך על משאב אין סופי). הלקח שלי הוא שחייבים להניח1 דטרמיניזם וסופיות, כל עוד המרצה לא אמר אחרת. עכשיו מגיע הקטע שבו מישהוא מספר בדיחה מתמטית. ____ 1 "הנחה" זו עוד דוגמא לכפל משמעות הנהדר שיש בעברית בכמה מושגים מדעיים. |
|
|
|
|
|
|
||
|
||||
|
מעלה המון תובנות בקשר לחלק מהשאלות שהועלו כאן, במיוחד הקשר של צ'רצ-טיורינג לגדל, ולמגבלות הפיסיקליות השונות (פלאנק ושות'). | |
|
|
|
|
|
||
|
||||
|
אני מצטרף להמלצה לקרוא את המאמר - תמיד דבר טוב - אבל לעניות דעתי הוא לא כל-כך מעניין, לא מדויק לפרקים, וחוטא בכתיבה שיווקית מופרזת מאוד. אם מישהו רוצה אפשר לפצוח בדיון סוער על הבעיות במאמר והשאלה אם Hypercomputation זה מעניין. (אגב, fair non-determinism לא מתחמק (כמובן) מהבעיות הקשורות באינסוף - קרא את הקטע עם הלמה של Koenig). |
|
|
|
|
|
|
||
|
||||
|
כן, הבנתי את זה בקריאה היותר מלאה. | |
|
|
|
|
|
||
|
||||
|
בבקשה! אבל נראה שלא הבנת אותי. המסר לא היה "אפשר לפתור בעיות מאוד מסובכות עם מכונת טיורינג", אלא "מכונת טיורינג יכולה לבצע כל דבר שאנו מסוגלים לחשוב עליו שנופל תחת הכותרת 'אלגוריתם"'. (אגב, הסרט באמת אינסופי, אבל מניחים תמיד שבשלב הקלט הסרט ריק (או מלא באפסים) פרט למספר סופי של מקומות, ולכן אם המכונה עוצרת גם הפלט סופי). ה"עוז" נובע בדיוק מכך שכל אלמנט אבסטרקטי שנראה שהוא חלק מהמונח "אלגוריתם" ניתן ליישום ע"י מכונת טיורינג. אם אפשר "להריץ משהו על חומרה אחרת", נסה לדמיין - מה עושה אותה חומרה? היא לא מבצעת סדרה של פעולות שמירה, שליפה, החלטה וחישוב-פשוט? מה עושה "מכונה" כלשהי, בכלל? כל הנקודה היא שלפחות בקונטקסט של קלט-פלט סופי ודיסקרטי, אף אחד עוד לא הצליח לחשוב על משהו שלא נופל בקטגוריות האלה, והאמת גם קשה (לי, לפחות, ונראה שגם לאחרים) לדמיין מה משהו כזה יכול להיות. שוב, אין פה הוכחה - אנו מנסים לפרמל מושג אינטואיטיבי. משפטי גדל דנים ביכולת של מערכת לוגית פורמלית להיות עקבית (לא מאפשרת להוכיח דבר והיפוכו) ושלמה (לכל טענה בשפה של המערכת, אפשר להוכיח או את הטענה או את שלילתה). אחד המשפטים מראה שכל מערכת סבוכה מספיק (מספיקה כדי לתאר את המספרים הטבעיים) אינה יכולה להיות גם עקבית וגם שלמה. משפט אחר, קשור, מראה שמערכת לוגית (שוב, מורכבת מספיק) איננה יכולה להוכיח את העקביות של עצמה (אם היא עקבית. אם לא, היא יכולה להוכיח כל דבר). משפטי אי-האפשרות של טיורינג הם דומים אך שונים. המשפט הבסיסי אומר שאין מכונת טיורינג המקבלת כקלט תיאור של אלגוריתם (מכונה אחרת) וקלט לאותו אלגוריתם, ומחליטה אם הפעלת אותו אלגוריתם על אותו קלט תיגמר לבסוף. (מכונת טיורינג, כפי שהגדרנו אותה, יכולה לבצע מיליארד צעדים ולעצור, אך היא עלולה גם לא לעצור לעולם - קל מאוד לכתוב תכנית מחשב שלא עוצרת). בעזרת משפט זה הוכיחו שפע של תוצאות שליליות במתמטיקה, לפיהן אין אלגוריתם המסוגל לפתור משוואות דיופנטיות או לבדוק אם חבורה (הנתונה ע"י יוצרים ויחסים) היא טריויאלית או לבדוק אם שני מרחבים תלת-ממדיים (הנתונים ע"י תיאור קומבינטורי של פירמידות מודבקות) הם זהים מבחינה טופולוגית. הדמיון בין המשפטים הוא באופי שלהם (מגבלות מסויימות של מערכות פרוצדורליות פורמליות) וגם באופי ההוכחות (קידוד של המערכות עצמן בשפה שהן פועלות בה). אני צריך עוד לחשוב אם יש קשר ישיר יותר של גרירה לוגית, צריך להיזהר פה קצת אבל אני אחשוב. בקשר לריבוזומים - הכי טוב שאודי יסביר בעצמו: |
|
|
|
|
|
|
||
|
||||
|
תודה. עכשו ברור יותר. עושה רושם שכמה מהמשפטים היסודיים ביותר של תחומי דעת מסויימים הם "חוקי אי אפשר": חוקי גדל, חוק אי הודאות של הייזברג, היפותזת צ'רצ'-טורינג. מעניין, על דרך השלילה האנשים הללו עלו על תובנה יסודית לגבי אופן פעולתם של דברים. |
|
|
|
|
|
|
||
|
||||
|
וכמובן גם בעית העצירה וחסם מהירות האור. | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
לגבי מודלי חישוב שאינם ניתנים לרדוקציה למכונת טיורינג רגילה, קיימים כמובן חישובים הסתברותיים, הניתנים לחישוב ע"י מכונת טיורינג הסתברותית (אם אתה במצב מספר 67 וקורא 1 תעבור למצב 112 בהסתברות 43 או למצב 86 בהסתברות 57. אם אתה קורא 0 תעבור למצב 98 בהסתברות 33 ולמצב 65 בהסתברות 67) וכן אלגוריתמים קוונטיים הניתנים לחישוב ע"י מכונת טיורינג קוונטית. (דטרמיניסטית או הסתברותית) אפשר כמובן לטעון שאלגוריתם הסתברותי או קוונטי הוא לא אלגוריתם אלא משהו אחר, אבל זה כבר עניין של הגדרה. |
|
|
|
|
|
|
||
|
||||
|
נכון, אבל זהירות - העניין באלגוריתמים הסתברותיים וקוונטיים נובע מיכולתם לחשב *ביעילות* בעיות קשות, לא (ככל הידוע לי) לפתור בעיות ש*אינן ניתנות לחישוב*. אם יש אלגוריתם הסתברותי המסוגל לבדוק אם גרף הוא 3-צביע (נניח), אז ודאי שיש גם אלגוריתם דטרמיניסטי המסוגל לעשות זאת, רק הרבה יותר לאט. ההישג העיקרי של המודלים הקוונטיים של חישוב הוא בפירוק *יעיל* של מספרים, שהיא כמובן בעייה טריויאלית מההיבט החישובי. אם מדובר על חישוביות, ולא סיבוכיות, אז חישוב הסתברותי איננו מעשיר את הרפרטואר, ואני סבור שגם קוונטי לא (ייתכן שאני טועה בנקודה זו, עבר זמן מאז התעניינתי בתחום). | |
|
|
|
|
|
||
|
||||
|
אתה לא טועה (מחשבים קוונטיים ניתנים לסימולציה ע''י מכונות טיורינג - הבעיה היא שהסימולציה איטית). | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שאתה צודק. עד כמה שאני זוכר, מכונת טיורינג לא יכולה לסמלץ במדוייק מכונת טיורינג קוונטית שנמצאת בסופרפוזיציה של כמה מצבים. ניתן לייצג קרוב בלבד. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שאתה מתכוון לומר שאם למכונה הקוונטית מותר להיות בסופרפוזיציה של כמה מצבים עם משקל ממשי לכל מצב, אז לא ניתן לסמלץ זאת בדיוק ע''י מכונה דטרמיניסטית שיש לה אפילו יותר מצבים, אחד לכל קומבינציה של מצבים קוונטיים, כי דרושים אינסוף מצבים לסימלוץ. אבל אני לא בטוח שזה משנה לשאלת ה''מה ניתן לחשב''. אם נכון לחשוב על מכונה קוונטית בסופרפוזיציה כנמצאת במספר מצבים, כל אחד עם משקל (אפילו ממשי), וכשהיא מתקדמת היא מגיעה לסופרפוזיציה של מצבים אחרים עם משקלות אבל באופן שכל מצב חדש (עם משקל חיובי) הוא נגיש ממצב ישן (עם משקל חיובי), אז לכל חישוב שלה יש חישוב חוקי של המכונה הקלאסית המתאימה ש''במקרה'' בוחר נכון בכל שלב לאן ללכת. שוב, השאלה היא רק אם החישוב הקלאסי הוא ''מסלול'' בגרף המסובך של החישוב הקוונטי, ואם יש איזושהי דרך לצאת מהמצב ההתחלתי (או אחד מהם, אם יש כמה) ולהגיע לתוצאה הסופית המבוקשת. |
|
|
|
|
|
|
||
|
||||
|
או אולי סתם שאלות מטופשות (אתה תשפוט): "משפט אחר, קשור, מראה שמערכת לוגית (שוב, מורכבת מספיק) איננה יכולה להוכיח את העקביות של עצמה (אם היא עקבית. אם לא, היא יכולה להוכיח כל דבר)." 1. האם ניתן להוכיח בתוך מערכת לא-עקבית את חוסר העקביות? (האם עצם זה שניתן להוכיח דבר והיפוכו מהווה את ההוכחה לכך שהמערכת היא אי-עקבית? אבל לפי זה גם ניתן להוכיח שהיא לא עקבית, ומכאן לא יוצא שהשאלה לא מוגדרת טוב או משהו כזה?) 2. אם ניתן להוכיח שמערכת היא לא-עקבית, האם ניסוח יותר מדוייק למשפט למעלה הוא, "לא ניתן להוכיח במערכת לוגית מורכבת מספיק שלגביה (או בתוכה) לא הצלחנו להוכיח (להראות?!) חוסר-עקביות כי היא עקבית" ? 3. האם ניתן להוכיח עקביות של מערכת כלשהו באמצעות מערכת חיצונית ומכילה אותה, ואם כן, מה הערך של הוכחה כזו, ובכלל מה ההבדל בין הוכחות תוך-שפתיות לחוץ-שפתיות? |
|
|
|
|
|
|
||
|
||||
|
1. כן. ההגדרה של מערכת לא עקבית היא שהיא יכולה להוכיח דבר והיפוכו. לכן, אי-עקביות (אם היא קיימת) ניתנת להוכחה בתוך המערכת. במצב זה, ניתן לראות שאפשר להוכיח באמצעות המערכת *כל* דבר (וגם את היפוכו), מה שכמובן הופך אותה ללא מעניינת. נכון שאפשר אז גם להוכיח שהיא לא עקבית וגם להוכיח שהיא כן עקבית (בהנחה שעקביות-עצמית בכלל ניתנת לניסוח בתוך המערכת, מה שלא תמיד המצב), כמו שאפשר להוכיח גם ש-X=X וגם ש=X שונה מ-X; זה לא נורא מעניין כי זה כבר לא נכון שמה שאפשר להוכיח הוא אמיתי. מובן מאליו שלוגיקאים מקווים מאוד שהמערכות בהן הם עובדים אינן כאלה, ולעיתים ניתן להוכיח זאת (באמצעות מערכות רחבות יותר). 2. לא, אין קשר ל"לא הצלחנו", הטענה היא שאי-אפשר. אבל אתה צודק, צריך לסייג ב"אם היא עקבית". 3. כן. הנה דוגמה: יש מערכת הנקראת "אקסיומות פֵּאָנו (מסדר ראשון) של תורת המספרים". זו תורה לוגית המאפשרת לדון במספרים הטבעיים, בחיבור ובכפל, ולהוכיח משפטים כמו "כל מספר ראשוני המשאיר שארית 1 בחלוקה ל-4 הוא סכום של שני ריבועים", וכו'. צריך להבין שלא כל טענה מתמטית בכלל ניתנת לניסוח בתוך המערכת הזו: למשל, הטענה "לכל פונקציה רציפה על הכדור יש נקודת שבת" היא כזו. לעומת זאת, הטענה "מערכת פאנו היא עקבית" דווקא כן ניתנת לניסוח כטענה בתוך המערכת - ברם, לפי גדל, אי אפשר להוכיח אותה במערכת זו. למרבה השמחה אפשר כן להוכיח אותה במערכת חזקה יותר, למשל אחת הנקראת ZF ומכילה אקסיומות של תורת הקבוצות. מה הערך של הוכחה כזו? פשוט, היא עוזרת לך להקטין את מספר הדברים בהם צריך להאמין. אם אתה מאמין ש-ZF עקבית, קיבלת במתנה שגם פאנו כזו. |
|
|
|
|
|
|
||
|
||||
|
2. אין צורך לסייג: אי-אפשר להוכיח עקביות, בין אם מפני שהמערכת לא עקבית, ובין אם מפני שהיא עקבית ואי-אפשר להוכיח את זה. | |
|
|
|
|
|
||
|
||||
|
זה סתם ניטפוק לא מעניין, אבל אם המערכת לא עקבית, למה היא לא יכולה להוכיח שהיא עקבית? פורמלית, היא כן, והיא יכולה גם להוכיח את ההיפך וזה כאמור לא ממש מעניין. -- (גזור וזרוק) -- אם המערכת היא T, ו-X מסמן איזושהי סתירה כמו "a וגם לא a", אז: T |= (X -> con(T)) כי אגף ימין הוא טאוטולוגיה, וגםT |= X כי T לא עקבית, ומכאן בגרסת מודוס-פוננס ליכיחות,T |= con(T) לא?
|
|
|
|
|
|
|
||
|
||||
|
יכול להיות שזו סתם קטנוניות טכנית, אבל הוכחות פורמליות לא עובדות עם טאוטולוגיות של תחשיב פסוקים? הטענה (a!=a --> B) איננה מהווה טאוטולוגיה בתחשיב הפסוקים, וממילא לא ניתן להשתמש בה כאקסיומה בהוכחה. אני חושב שעל מנת להראות שסתירה בתחשיב יחסים מוכיחה כל טענה אפשר לשחזר את הוכחת משפט השלמות של גדל, כאשר לכל טענה A ניתן לטעון ש "כל מודל של T מקיים A" (באופן ריק). | |
|
|
|
|
|
||
|
||||
|
אני לא בטוח שצריך דווקא את תחשיב הפסוקים, עקרונית כל מה שדרוש הוא שפה ומערכת הוכחה. לרוב דורשים שמערכת ההוכחה תהיה sound ושלמה, אבל לצורך הזה אני לא חושב שאפילו צריך שלמות. במערכת הוכחה סבירה, כלל הגזירה הבאה (הוכחה על דרך השלילה) יהיה אקסיומה, או מסקנה מכללים אחרים: אם T, ~f |- g ו-T, ~f |- ~g אזT |- f ונראה לי שזה כל מה שדרוש. (למעלה השתמשתי בטעות ב-=| במקום ב -|, זה לא משנה הרבה אך התכוונתי להסקה פורמלית, לא לנכונות בכל מודל. אולי זה מה שבלבל).
|
|
|
|
|
|
|
||
|
||||
|
חשבתי על זה עוד קצת, אבל עדיין נראה לי שיש איזו בעיה עקרונית. הרי מערכת ההוכחה היא "טיפשה". היא מסוגלת לזהות רק סתירות של תחשיב פסוקים (כי היא כוללת את הטאוטולוגיות של פסוקים כאקסיומות). ברור שאם כבר ידוע ש T -מוכיחה- טענה ושלילתה אז ניתן להוכיח הכל, אבל סתם מכך שיצרנו תורה לא עקבית (למשל, תורה של מרחב וקטורי ממימד n יחד עם אופרטור שהינו חח"ע אבל לא על) עוד אין לנו סדרת הוכחה. בשביל להראות שמספיק שב T יש סתירה על מנת לייצר הוכחה של כל טענה יש לטעון שלפי קומפקטיות יש לנו אוסף סופי של טענות שבהן כבר יש סתירה, ומשם בעצם לשחזר את הוכחת משפט השלמות. רק במקרה שהסתירה ב T נובעת מסתירה של תחשיב פסוקים אז "יש לנו מזל" וההוכחה נעשית מובנת מאליה. אבל באוסף הטענות שכולל את האקסיומות של מרחב וקטורי ממימד n בצרוף הטענה על אופרטור חח"ע ולא על אין שום סתירה של תחשיב פסוקים. בקיצור, אם אני לא טועה יש הבדל בין העובדה (הטריוויאלית לגמרי) שאם מערכת מוכיחה טענה ושלילתה אז היא מוכיחה כל טענה, לבין העובדה שאם במערכת -קיימת- סתירה (קרי, היא איננה עקבית, אין לה שום מודל) אז ניתן לייצר ממנה הוכחה לכל טענה. הוכחת העובדה השניה היא כבר פחות או יותר משפט השלמות. | |
|
|
|
|
|
||
|
||||
|
רגע, נדמה לי שהקושי הוא שאתה מגדיר מערכת לא-עקבית ככזו שאין לה מודל, ואני הגדרתי מערכת לא-עקבית ככזו שמוכיחה דבר והיפוכו. במערכות שלמות, כפי שציינת, זה אותו דבר. אני חושב שנתקלתי בשתי ההגדרות. | |
|
|
|
|
|
||
|
||||
|
sound = נאותה. (סליחה על ההפרעה, תמשיכו). | |
|
|
|
|
|
||
|
||||
|
חשבתי שמדובר על הוכחה מבחוץ (במערכת עקבית) שהמערכת (הלא-עקבית) ''שלנו'' היא עקבית, וזה כמובן בלתי אפשרי. אבל זה לא מאד מעניין. | |
|
|
|
|
|
||
|
||||
|
אודי שפירו בעבודה מעניינת מאד, מסתבר שהתכניות שלו הרבה יותר מעשיות ממה שחשבתי: |
|
|
|
|
|
|
||
|
||||
|
התכניות שלו לזכות בפרס נובל? | |
|
|
|
|
|
||
|
||||
|
אולי :-) אבל התכוונתי למעשיות של תכניותיו לגבי מחשבים ממולקולות ביולוגיות. | |
|
|
|
|
|
||
|
||||
|
נדמה לי שזה כבר לא בגדר "מעשיוֹת" :) | |
|
|
|
|
|
||
|
||||
|
אני קורא בעיון את הדיון של החברים המלומדים והחלטתי שאתם הכתובת לבקש עזרה.אני זקוק לכל חומר שיכול לעזור לי לערון בצורה יפה ומסודרת את ההיסטוריה של "מדעי המחשב"-הדיסציפלינה.לא ההיסטוריה של מכונות החישוב ולא ההיסטוריה של התכנות או כל דבר אחר דומה.אלא של המדע עצמו: המושגים המופשטים, התיאוריה המתימטית, הדמויות החשובות וכו, ללא קשר למחשב עצמו. כל עזרה תתקבל בברכה. בתודה מראש: דודי. |
|
|
|
|
|
|
||
|
||||
|
סליחה שאני מתערב, וסליחה על האורך, אבל יש קשר ישיר. אפשר להוכיח את משפט גדל על ידי משפט אי העצירה. ההוכחה נוסחה על ידי טיורינג עצמו. הרעיון בנפנוף ידיים, הוא כדלקמן: קיימת פונקציה חד חד ערכית מאוסף כל מכונות הטיורינג למספרים הטבעיים. (לא זוכר אותה, אבל היא קיימת ומנוסחת היטב. תאמינו לי). קיימת פונקציה בין מצבים שונים של מכונת טיורינג לבין המספרים הטבעיים. בינהם - מצב העצירה. קיימת פונקציה בין כל הקלטים של מכונת טיורינג לבין המספרים הטבעיים. מכל הטררם הנ"ל יוצא, שהמשפט "מכונת טיוריג M עוצרת מתישהו כשהיא מקבלת פלט T" הוא פסוק בתורת המספרים. שוב, זה קצת נפנוף ידיים, אבל זה הרעיון. גם המשפט ההפוך, "המכונה M אינה עוצרת לעולם כשהיא מקבלת פלט T" הוא פסוק בתורת המספרים עכשיו בא הקטע המגניב באמת: 1)קיימת תוכנת מחשב Ma, שכידוע שקולה למכונת טיורינג, שמקבלת טקסט באנגלית, ומחליטה האם הטקסט הנ"ל הוא הוכחה תקנית (באמת כתבו אותה!) - כלומר - האם הטקסט מורכב מאקסיומות בהתחלה, משפט בסוף, וקשרים לוגיים נכונים בין כל משפט למשפטים הקודמים לו. 2) קיימת תוכנת מחשב Mb, שמייצרת את כל הטקסטים הסופיים, אחד אחרי השני (היא עובדת המון, אבל כל טקסט סופי, יבוא יומו והיא תייצר אותו) 3) נתן לMb לעבוד, ולשלוח טקסטים לMa, שתבדוק האם הטקסט הוא הוכחה תקנית. 4) נוסיף לMa שורות שיבדקו, במקרה שהיא מצאה שטקסט מסויים הוא הוכחה, האם האקסיומות שלו הם של תורת המספרים, והמשפט הסופי הוא "M עוצרת על T" 5) נוסיף עוד שורות שיבדקו מייד לאחר מכן, האם האקסיומות שלו הם של תורת המספרים, והמשפט הסופי הוא "M *לא* עוצרת על T" אם לכל הפסוקים בתורת המספרים, או לשלילתם, היתה הוכחה, אזי תוכנת המחשב (מכונת טיורינג) שבנינו הייתה מכריעה את בעיית העצירה. כיון שאי אפשר להכריע את בעיית העצירה, אזי משפט גדל נכון. חמוד, לא? |
|
|
|
|
|
|
||
|
||||
|
כן. | |
|
|
|
|
|
||
|
||||
|
ניסיתי פעם לייצר LIFE חד-ממדי. יצא די טריוויאלי, כמובן. נזכרתי בזה כי גרפית זה מאוד דומה לציור שעל עטיפת הספר של וולפרם (ייצגתי כל דור כשורה חדשה מתחת לשורה שייצגה את הדור הקודם). | |
|
|
|
|
|
||
|
||||
|
לא רק גרפית: הציור שעל עטיפת הספר הוא בדיוק התפתחות הדורות של אוטומט חד-ממדי דמוי-Life. | |
|
|
|
|
|
||
|
||||
|
התזה של צ'רץ' לא הוכחה עדיין? אין לי סבלנות לחכות עוד סמסטר לקורס אוטומטים. ויש שימוש מעשי, בניגוד לתיאורטי, למכונת טיורינג? |
|
|
|
|
|
|
||
|
||||
|
הגיע הזמן שאני לא אגיב עד שאני לא קורא את כל התגובות באותו הפתיל... | |
|
|
|
|
|
||
|
||||
|
אם אתה לומד בת''א, ויש לך אפשרות, אז בחר בשעור של טרסי (ולא של האלטרנטיבה). | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
לא. | |
|
|
|
|
|
||
|
||||
|
צ'רץ' לא נידון כלל, למיטב ידיעתי, בקורס אוטומטים ושפות פורמליות (אש"פ, בשבילך). מכונות טיורינג וכל הגאז' הזה שייכות לקורס בחישוביות (המלצה: ד"ר ארז פטרנק). | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |