בתשובה להאייל האלמוני, 04/01/07 12:51
כמה תווים נקראים? 427764
זה שונה, אבל זה לא מה שעושה את ההבדל. הראש האנושי מסוגל (לפחות בפעם האחרונה שבדקתי) לקרוא רק מספר *סופי* של תווים מתוך הסרט בכל רגע נתון. כלומר, אפשר לחשוב על הראש האנושי כאילו יש לו k ראשים קוראים/כותבים במקום האחד המסכן של מכונת טיורינג. לכן אפשר להגדיר מודל "משופר" של מכונת טיורינג, שיש לו k ראשים קוראים/כותבים.

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

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

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

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

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

בקשר למצע הפיזי: אני לא יודע מה זה "תרגיש". באשר ל"תפעל" - השאלה היא אכן האם ניתן להמיר את כל ה"קלט" שהאדם מקבל לקלט שמכונת טיורינג יודעת לעבוד איתו - אפסים ואחדות. זו שאלה שעל הפיזיקאים לענות עליה, ולי אין תשובה טובה בשבילה. זכור רק שעד עתה, ה"אפסים והאחדות" הללו עובדים לא רע - בשורה התחתונה, אלו אפסים ואחדות שהמצלמה הדיגיטלית עובדת איתם, ואלו גם אפסים ואחדות שמסך המחשב מקרין.
כמה תווים נקראים? 427824
למה שניכם מניחים שהזמן שלוקח לראש של שתי מכונות לקרוא תו הוא זהה? (ז"א, למה בכלל שניכם מניחים שהזמן זהה לשני תווים שונים באותה מכונה? ז"א, למה הוא מניח, ולמה אתה לא מעמיד אותו על הטעות שלו ומסביר לו שזה בכלל לא משנה?)
כמה תווים נקראים? 427827
אני לא הצבתי כלל הנחה כזאת.
כמה תווים נקראים? 427830
לא אתה כתבת "הרי אם זה ייקח לה יותר זמן לכל יחידת זמן, היא תהיה כל הזמן בפיגור הולך וגדל"?
כמה תווים נקראים? 427833
כן, אז?
כמה תווים נקראים? 427869
לא ראיתי שהוא מניח הנחה כזו, או שיש לה חשיבות (כפי שאתה עצמך אומר, אין לה). הוא דווקא מצביע על נקודה חשובה ומעניינת: היחס בין הזמנים שנדרשים לשתי המכונות עשוי לגדול יותר ויותר כתלות בקלט (נניח, אם נגדיל את הקלט פי 2, נגדיל את היחס בין הזמנים פי 4). זה לא משנה כל עוד מדברים על שאלות של כריעות מול אי כריעות, אבל כשמדברים על זמן ריצה זה הופך להיות חשוב. אחת מהסיבות שבגללן בוחרים פונקציות פולינומיות בתור מדד לחישוב יעיל (במקום, נניח, פונקציות שהן פולינום מחזקה נמוכה יחסית) היא ששינויי מודל כמו זה שהוא מציע לא ישפיעו.
כמה תווים נקראים? 428101
אם יש לך שתי מכונות, לאחת יש אלף ראשים וכל אחד מעבד את הקלט בקצב של תו אחד בשניה, ולשניה יש ראש אחד והוא מעבד את הקלט תו אחד באלפית שניות, אז היחס בין הזמנים יהיה זהה. לעומת זאת, אם מכונה אחת עם ראש אחד תעבד את הקלט בתו אחד לשניה, ומכונה נוספת עם ראש אחד תעבד את הקלט בשני תווים בשניה, אז יווצר ביניהם יחס זמנים (למרות שמספר הראשים זהה). בקיצור, איפה כאן הנקודה המעניינת?
כמה תווים נקראים? 428109
הניתוח שלך די נאיבי, ומניח שה''תרומה'' היחידה של הראשים היא מהירות ''עיבוד קלט'' (ראש אחד מעבד תו בשנייה, שני ראשים מעבדים שני תווים בשנייה), אבל זה לא בהכרח נכון. אם יש לך מכונה בעלת שני ראשים, כדי לסמלץ אותה באמצעות מכונה בעלת ראש אחד אתה צריך לגרום לראש האחד הזה ''להתנהג'' כמו שני הראשים. בפרט, אם שני הראשים נמצאים רחוק מאוד זה מזה על הסרט, הראש האחד יצטרך להתרוצץ שוב ושוב בין שני המקומות המרוחקים הללו, ולבצע המון תנועות ששני הראשים לבדם לא היו צריכים לעשות.
כמה תווים נקראים? 428111
ועדיין, הזמן שהראש האחד יתרוצץ בין שני המקומות ויבצע את כל הפעולות יכול לקחת אלפית מהזמן שיקח לשני הראשים לבצע את הפעולות שלהם. אני עדיין לא רואה כאן נקודה מעניינת (אלא אם כן הנקודה המעניינת היא שחומרה טובה יותר תעבוד בד''כ מהר יותר מחומרה טובה פחות, אבל זה לא ממש מעניין, וממש לא קשור למכונות טורינג)
כמה תווים נקראים? 428143
מה שמעניין כאן הוא שיש לאורך הקלט חשיבות. אם המכונה הדו-ראשית מעבירה את אחד הראשים לסוף הקלט ואת השני משאירה בהתחלה, ומכאן והלאה מזיזה כל ראש צעד ימינה וצעד שמאלה לסירוגין ועושה זאת במשך n פעמים (כש-n הוא גודל הקלט), אז המכונה עם הראש הבודד תצטרך לבצע n זגזוגים בין שני ראשים שהמרחק ביניהם הוא n - כלומר יידרשו לו בערך n בריבוע צעדים.

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

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

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

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

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

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

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

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

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

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

כל העיסוק ב"הכפלת החומרה" אכן לא שייך לדיון הזה (כמו גם כל שאר ההודעה שלך - אבל היופי בדיונים הוא שהם גולשים למקומות שלא שייכים בהכרח למאמר המקורי) אבל כאמור, במאמר הבא אין הרבה מה לומר על זה - רק שבוחרים לזהות חישוב פולינומי עם חישוב יעיל בין היתר כדי לא להיות תלויים בפרטי מימוש כמו אלו.
כמה תווים נקראים? 428265
אפשר להגיד שמיון מיזוג עדיף על מיון בועות גם על פנטיום וגם על אטארי רק בגלל שאפשר להגיד גם על מחשב פנטיום וגם על מחשב אטארי מהו הזמן (הממוצע) שלוקחת פעולת עיבוד בודדת. בלי זה, הקביעה שלך פשוט לא נכונה.
כמה תווים נקראים? 428268
לי נראה שמספיק לומר ש*קיים* זמן ממוצע שלוקחת פעולת עיבוד בודדת. אם מתעקשים, אפשר לפרוט את האלגוריתמים לפרוטות עד שמוצאים את פעולות העיבוד הבסיסיות ששניהם עושים ורואים שהן אותו דבר ושמיון מיזוג מבצע פחות מהן, אבל זו שוב התעסקות בטפל.
כמה תווים נקראים? 428270
כן, נכון, מספיק לומר שקיים זמן ממוצע שכזה.
כמה תווים נקראים? 428271
אז קצת מעניין אותי לראות דוגמה למצב שבו לא ניתן לומר דבר כזה.
כמה תווים נקראים? 428274
אני אסביר את עצמי בדוגמא. בו ניקח את הדוגמא של מיון בועות מול מיון מיזוג. נניח שהמימוש שלך הוא כזה שאתה מבצע את מיון הבועות ב
5N^2
פעולות והמימוש של יון המיזוג הוא של
20N*LN(N) +1
עכשיו, אם נספור פעולות, נגלה שאם גודל הקלט שלנו גדול מתשע אלמנטים מיון המיזוג יהיה עדיף. אבל, בו נניח שהזמן שלוקח למכונה הראשונה לביצוע כל פעולה הוא חצי מהזמן שלקחה לה הפעולה הקודמת, בעוד שהזמן שלוקח למכונה השניה לבצע פעולה הוא כפול מהזמן שלקחה הפעולה הקודמת. אז (אם לא התבלבלתי) גם אם נניח שהזמן שלוקחת הפעולה הראשונה במכונה הראשונה הוא פי אלף מהזמן שלוקחת הפעולה הראשונה במכונה השניה, עדיין, המכונה הראשונה תעבוד מהר יותר מהשניה כשהקלט יהיה בן שני אלמנטים או יותר (אז מה עשינו בזה? באמת שכלום. עוד מעט יבוא לכאן מר ו. ויוסיף לי תגובה ריקה מתחת).
כמה תווים נקראים? 428283
אני קצת מבולבל. מי זו המכונה הראשונה? מי זו המכונה השניה? מה אתה טוען, בעצם?
כמה תווים נקראים? 428286
המכונה הראשונה היא זאת שמבצעת מיון בועות, השניה מבצעת מיון מיזוג.

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

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

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

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

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

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

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

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

בסופו של דבר, זאת טענה ממש טריויאלית, מאד מוזר לי שהייתי צריך להוכיח אותה, עוד יותר מוזר לי שגם אתה, גם אביב וגם דורון לא מבינים אותה/לא מסכימים איתה, והכי מוזר לי שאחרי כל הדיון הזה היא עדיין נראית לך כמו "הסחפות".
כמה תווים נקראים? 428319
אני תמיד חשבתי שבסיבוכיות משווים את מספר הפעולות הנדרשות כפונקציה של אורך הקלט, ושואלים על האסימפטוטיקה. כל עוד יש מספר סופי של סוגי פעולות והזמן הנדרש לכל פעולה כזאת הוא חסום, זה שקול לשאלות על האסימפטוטיקה של זמן הריצה, לא?
כמה תווים נקראים? 428324
כן, גם אני חשבתי ככה.
כמה תווים נקראים? 428325
הבנתי שזה גם מה שגדי אומר, לא?
כמה תווים נקראים? 428327
לא יודע (מתברר שאנחנו לא ממש מבינים אחד את השני, אז אני האחרון שיכול להיות הפרשן שלו).
כמה תווים נקראים? 428329
במשמעות המקובלת של סיבוכיות, הסיבוכיות של חישוב אחד שווה לסיבוכיות של חישוב שני אם הזמן של החישוב השני הוא לכל היותר מכפלה קבועה של הזמן של החישוב הראשון, ולהפך. אז אם ''הזמן שלוקח לפעולה'' של מכונה אחת הוא לכל היותר מכפלה קבועה של ''הזמן שלוקח לפעולה'' של מכונה אחרת, אז אין ל''זמן שלוקח לפעולה'' כל השפעה על הסיבוכיות.
כמה תווים נקראים? 428331
ובשפה שאני מדבר בה, הפסוקית שבאה בין ''אם'' ל''אז'' במשפט השני שלך היא ''הנחה''.
כמה תווים נקראים? 428332
תראה, בתחום הזה מודדים את הזמן בפעולות של מכונת-טיורינג. השאלה כמה זמן לוקחת פעולה אחת יכולה להיות רלבנטית רק כשמסמלצים מכונה אחת באמצעות אחרת, כי אז מודדים את הזמן בפעולות של המכונה הבסיסית יותר.
כמה תווים נקראים? 428333
את ההנחה שהזמן שלוקחת פעולה אחת הוא קבוע/ חסום/ בעל התפלגות ידועה מראש ומתנהגת יפה חייבים להניח כי אחרת אין למספר הפעולות של מכונת הטיורינג שום משמעות (אבל, כששואלים אם המספר הוא סופי או לא חייבים רק להניח שהזמן שלוקחת פעולה הוא סופי).
כמה תווים נקראים? 428339
אולי אני מבין מאיפה חוסר ההסכמה. מה שמפריע לך הוא ש"מדידת זמן" במכונת טיורינג היא בעצם ספירת צעדי חישוב, ולא מדידה של זמן אמיתי?

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

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

אם לדעתך זה לא אומר כלום - לא נורא. לא צריך להמשיך את הדיון, ואיש בדעתו יחיה.
כמה תווים נקראים? 428340
באמת אין שום משמעות. זה מודל. אין משמעות לעצם השאלה ''הזמן שלוקחת פעולה'', כי ''פעולה אחת'' היא יחידת הזמן שלנו מלכתחילה. אם תגדיר אותה בשניות, עדיין תצטרך להגדיר שנייה, ולהסביר למה שנייה של מ''ט אחרת שווה לשנייה של מ''ט אחרת (ולא, נאמר, שאחת נייחת ביחס אלינו והשנייה משייטת במהירות קרובה למהירות האור, או השד יודע מה).
כמה תווים נקראים? 428348
אם אתה לוקח את מכונת טיורינג בתור מודל שאין בו משמעות לזמנים, אז ברגע שהצלחת לסמלץ מכונה אחת בעזרת אחרת, שתי המכונות זהות. אם אתה מייחס משמעות לזמנים, אתה חייב להניח משהו לגבי הזמנים (וגם ההנחה ש''פעולה אחת'' היא יחידת הזמן שלך היא הנחה). אי אפשר לאכול את העוגה ולהשאיר אותה שלמה.
כמה תווים נקראים? 428352
אין משמעות ל"זמנים", אבל יש משמעות למספר צעדי החישוב. אם חישוב במודל אחד לוקח פי n יותר צעדים מאשר במודל השני, אי אפשר להגיד ששני המודלים זהים, ואפילו לא שאפשר להתעלם מההבדל ביניהם.
כמה תווים נקראים? 428359
רגע, עכשיו יש לי מודל חדש, שעושה שני צעדים במקום כל צעד של המודל הקודם, ז"א ספרתי את הצעדים ויצא לי 28,246. לא תרשה לי להתעלם מההבדל ביניהם?
כמה תווים נקראים? 428364
בוא נתכנס לתגובה 428361.
כמה תווים נקראים? 428373
''זמן'' במכונת-טיורינג מוגדר כ''מספר הפעולות שהמכונה ביצעה''. זו לא הנחה, זו הגדרה. (ויש לה משמעות לא יותר ולא פחות מלכל הגדרה.)
כמה תווים נקראים? 428377
וכשאנחנו רוצים להסיק מסקנות מהמודל לעולם האמיתי (כמו שניסו להעשות בתחילת הפתיל) צריך לתת משמעות בעולם האמיתי לזמן במכונת טיורינג (או להתעלם מהמושג).
כמה תווים נקראים? 428378
אה, לשם אתה חותר? בסדר, אני מסכים.
כמה תווים נקראים? 428381
בעולם האמיתי זו לא בעיה. קשה לי אפילו לדמיין מכונה פיסית שמסמלצת מ''ט בצורה כזו שכל צעד מ''ט לוקח זמן אקספוננציאלי באורך הקלט. לכן מ''ט זה מודל כל-כך שימושי בניגוד למודלים שקולים אחרים.
כמה תווים נקראים? 428383
בעולם האמיתי זה לא בעיה בגלל שמניחים הנחות לגבי הזמן של כל פעולה. ללא הנחות, המודל היה פשוט לא שימושי.
כמה תווים נקראים? 428384
לא-לא. אתה לא יכול להניח הנחות בעולם האמיתי. אתה יכול רק לקוות שהעולם תואם מספיק את המודל שלך. מסתבר שבכל/רוב מכונות החישוב שאנחנו בונים, זמן פיסי הוא באמת פרופורציונאלי פחות-או-יותר לזמן מ"ט. לכן מ"ט זה המודל הסטנדרטי למכונות חישוב ולא כל-מיני מודלים מופרעים שאני יכול להעלות על דעתי.
כמה תווים נקראים? 428385
反义词
כמה תווים נקראים? 428386
מ"ט=מכונת-טיורינג
כמה תווים נקראים? 428337
ה"היסחפות", לטעמי, היא שאתה אומר שאם סופרים מספר צעדים של משהו, הוא הופך להיות משהו אחר.

נניח שיש לי מכונית ושמד סיבובי המנוע בתוכה מכוסה בסלוטייפ. עכשיו בוא נניח שאני מוריד את הסלוטייפ. האם קיבלתי מכונית שונה?
כמה תווים נקראים? 428345
זה‏1 לא מה שאמרתי (וחוץ מזה, נראה לי שממש לא הבנתי את המשל שלך).

1 מה שאמרתי הוא שאם יש הנחות נוספות על מושג מתמטי אז כבר מדובר על מושג אחר, שמכיל בתוכו את המושג הקודם. למשל, חבורה שהמכפלה שלה היא הופכית היא חבורה אבלית. חבורה אבלית היא חבורה, אבל חבורה היא לא בהכרח חבורה אבלית.‏2

2 ואני משוכנע שאתה יודע את זה. הרי אתה מככב ב http://he.wikipedia.org/w/index.php?title=%D7%97%D7%...
כמה תווים נקראים? 428353
אוקיי. מה ההנחה הנוספת שיש על המכונה במקרה הזה? כזכור, אין שום הנחות לגבי הזמן שלוקח למכונה לבצע צעד חישוב.
כמה תווים נקראים? 428360
לא יודע, "מניחים שכל צעד שמכונת הטיורינג עושה לוקח יחידת זמן אחת" זה לא הנחה (תגובה 428292)?
כמה תווים נקראים? 428367
לא, זו הגדרה. אתה יכול לסלק את ה''מניחים'' אם הוא מפריע לך ולהחליף את המשפט ב''מגדירים את יחידת הזמן הבסיסית שלנו בתור צעד של המכונה'' (שזה מה שהתכוונתי לומר).
כמה תווים נקראים? 428389
האם מה שמפריע לך היא ההנחה שהזמן (ב"עולם האמיתי" יהא אשר יהא) שלוקח לבצע פעולה הוא קבוע (או חסום ע"י קבוע)? אולי זו ההנחה שכולם בדיון מניחים כמובנית מאליה, חוץ ממך?
כמה תווים נקראים? 428424
כן, קבוע, חסום על ידי קבוע, מתפלג יפה, משהו. ברור לי שכולם כאן מניחים את זה כמובן מאליו, לא ברור לי למה, ולמה הם מתעקשים שהם לא.
כמה תווים נקראים? 428444
לא נראה לי שמישהו התעקש שהוא לא מניח את זה, אלא שלא ברור למה זה רלוונטי לדיון - בפרט, למה זה משנה את המודל של מכונת הטיורינג ולמה זה חשוב רק כשמודדים סיבוכיות זמן ולא בודקים כריעות. הרי אם פעולה בסיסית במכונת טיורינג עלולה לקחת אינסוף זמן בעולם האמיתי, זה חשוב גם לשאלות של כריעות.
כמה תווים נקראים? 428446
אני לא יודע על מה ולמה התעקשתם. אני יודע *בדיוק* על מה ולמה אני התעקשתי, הסברתי משהו שהוא פשוט (ממש פשוט) ונכון (ממש נכון), ניסחתי את זה בשש צורות שונות. נימקתי. הוכחתי. הדגמתי. הסברתי. חזרתי והסברתי. אתם התעקשתם, מסיבה שעד רגע זה לא ברורה לי, מנימוקים ששייכים לדיון אחר לגמרי, לתקן אותי. הייתי מציע לכם בפעם הבאה לנסות ולהבין את מה בדיוק אתם מתקנים לפני שתתקנו (ולגבי עצמי, הייתי מציע לעצמי לא לכתוב יותר שום דבר "מקורי" באייל‏1. נראה לי שגם אם אני אכתוב ש 3+2 יוצא 5, מישהו יקפוץ ו"יתקן" אותי תוך כדי ציטוטים מההרצאה האחרונה במאקרוכלכלה או בספרות השוואתית שהוא נכח בה).

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

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

(הדיון על הורדת והוספת ראשים הוא מיותר בכל מקרה אם אנו עוסקים בכריעות. מה שאמרתי הוא שההבדל מעניין כאשר עוברים לעסוק בסיבוכיות.)
off with you head! 428449
אני מבקש בכל לשון של בקשה לעצור את התדרדרות רגע אחד לפני שעוברים להסרת ראשים.
כמה תווים נקראים? 428453
ממש לא יפה לכתוב כך על סמיילי. הדבר האחרון שאתה יכול להגיד זה שלא נעים לקרא אותו כי הוא כותב בשפה נקיה בלי הצטעצויות ובדיחות קרש אתה יכול שלא לאהוב את סגנון ההתדינות הפרטני שלו אבל את זה היתה חייב לגלות לפני הדיון ולא בסוף
כמה תווים נקראים? 428328
תגובה 428319 מקובלת עליך?
כמה תווים נקראים? 428338
כן. הטענה שלי היא ש"פעולה" הוא מושג מורכב שמסוגל להחביא בתוכו דברים שתלויים בגודל הקלט.

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

איך זה מתקשר למכונות הטיורינג החד-ראשית והדו-ראשית? בכך שאם מציגים אלגוריתם כלשהו שמשתמש ביכולות של המכונה הדו-ראשית, הרי שמה שנראה לנו כמו "פעולה בסיסית" במכונה הדו-ראשית עשוי לקחת זמן *שתלוי בגודל הקלט* במכונה החד-ראשית.
כמה תווים נקראים? 428342
מעניין. אבל למעשה כשמדברים על "כפל" מדברים על כפל של X ביט או משהו כזה, לפחות מבחינה מימושית, ולכן מספר הפעולות עולה כשהקלט מתארך תגובה 193615.
כמה תווים נקראים? 428354
''מספר הפעולות עולה כשהקלט מתארך'' זה מה שאמרתי.
כמה תווים נקראים? 428356
ממש לא. כתבת שפעולה בסיסית תלויה באורך הקלט. לא שצריך יותר פעולות בסיסיות לטפל בקלט ארוך יותר.
כמה תווים נקראים? 428363
לא. כתבתי ש''פעולה'' (לא ''פעולה בסיסית'') היא מושג שיכול להחביא בתוכו פעולות בסיסיות יותר, ומכיוון שמספר הפעולות הזה עשוי לגדול עם אורך הקלט, ''פעולה'' באופן כללי יכולה להיות תלויה באורך הקלט.
כמה תווים נקראים? 428368
" כשאתה כופל שני מספרים אתה בדרך כלל רואה את זה בתור "פעולה בסיסית" שהיא יחידת הספירה הקטנה ביותר"
==> כפל היא פעולה בסיסית.
"שככל שהמספרים גדולים יותר, כך הכפל שלהם ייקח יותר זמן."
==> כפל תלוי באורך הקלט.

ומכאן - פעולות בסיסיות תלויות באורך הקלט.

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

בגלל כל השאלות האלה היה מי שטען ש MIPS הוא ר"ת של Meaningless Index of Performance of Systems.
כמה תווים נקראים? 428376
עתידם עמנו עדיין: מעבדים מודרניים הם למעשה ליבת RISC שמסמלצת מעבד וירטואלי.
כמה תווים נקראים? 428344
סליחה מראש על גסות הרוח: תמהני אם עוד מישהו בקהל מוצא את השאלות האלה לדבר המשעמם ביותר מאז "מלחמה ושלום".
כמה תווים נקראים? 428355
''מלחמה ושלום'' דווקא די מעניין כל עוד טולסטוי לא נגרר לדיונים על מהות ההיסטוריה.
סקר! סקר! 428357
כמה תווים נקראים? 735450
האמת שדווקא קראתי עכשיו בעניין רב את כל הפתיל הזה. לא הבנתי כמעט כלום, אבל תמיד מצחיק לראות את סמיילי מתכתש עם אנשים חכמים שלא מבינים מה הוא רוצה. הקסם, כמובן, זה שמבחינה טכנית הוא תמיד צודק.
כמה תווים נקראים? 735470
לא כל מה שמשעמם הוא לא נכון.

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

א. גרפיקה של משחקים,
ב. כריה של מטבעות קריפטוגרפיים,
ג. חישובים לצורך בניית תוכנות AI שמבוססות על סקירה של נתונים שכמותם "אסטרונומית".
כמה תווים נקראים? 735472
המעבדים הגרפיים שונים ממעבדי RISC: יש להם המון ליבות חלשות יחסית ולכן הם יכולים לחשב במהירות רבה יותר חישובים שאפשר לחלק לחלקים קטנים ובלתי תלויים.
כמה תווים נקראים? 428255
זה כן קינטור מיותר. גדי מבין טוב מאוד שמכונת טיורינג חד ראשית שקולה למכונה דו ראשית מבחינת כוח החישוב (מכונה אחת לא יכולה לחשב משהו שהשניה לא יכולה). להגיד בצורה פסקנית (כמעט דוגמטית) שכל מכונות הטיורינג שניתן להעלות על הדעת זה אותו הדבר *לכל דבר ועניין נקודה* זה כבר הגזמה מיותרת. המודל של מ"ט לא דטרמניסטית (למשל) הוא כן מודל מעניין בהקשר של דיון על סיבוכיות, למרות שניתן לסמלץ אותה באמצעות מ"ט דט'.
כמה תווים נקראים? 428259
אין לי ספק שגדי יודע את זה טוב ממני. מציק לי שהוא לא מסביר את זה לאלמוני שנראה שלא ממש הבין את זה.
כמה תווים נקראים? 428166
אגב, יש איזה מספר של ראשים שמעליו, למסמלץ מכונה עם מספר גדול עוד יותר של ראשים כבר לא עולה יותר מבחינת הסיכוכיות?
כמה תווים נקראים? 428190
זו שאלה מעניינת (טוב, לא *עד כדי כך* מעניינת) שעליה אין לי תשובה. הניחוש שלי: לא.
כמה תווים נקראים? 428192
הסיבה שזה נראה לי מעניין זה כי מכונה כזו יכולה להיות מודל חישובי פשוט-יחסית (בלי אריתמטיקה) שכן שקול בדיוק מבחינת הסיבוכיות להפשטה של מחשב מודרני.
כמה תווים נקראים? 428194
יש כבר מודל דומה - מודל ה-RAM, שמזכיר מחשב מודרני, עם רגיסטרים והכל. אפשר ללמוד משהו על כמה התיאורטיקנים של מדעי המחשב מתעניינים בו אפשר ללמוד מהפסקה שבה פרופ' עודד גולדרייך בוחר לפתוח את תת הפרק שעוסק במודל הזה בחוברת הקורס של "תורת החישוביות" בטכניון:

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

אני, אגב, מסכים. חישוביות הוא קורס מרתק, אבל יש בו תרגול אחד משעמם פחד - זה שבו מציגים את מודל ה-RAM.
כמה תווים נקראים? 428195
אני מכיר את המודל הזה ומסכים עם מה שאתה אומר ומצטט עליו. הוא מסובך מדי. אם רוצים גישה ישירה, צריך כתובות, ואם צריך כתובות, אז צריך מספר אינסופי של ערכים לכל תא בסרט, ואם יש מספר אינסופי כזה של ערכים אז פונקצית צעדים פשוטה לא מספיקה, צריך אריתמטיקה, ואתה מוצא את עצמך עם מודל שבינו לבין מודל תיאורטי פשוט ומופשט אין הרבה. התאכזבתי ושאלתי את עצמי "מה, אין מודל _פשוט_ ששקול לו מבחינת הסיבוכיות?"
כמה תווים נקראים? 428196
אוקיי, אבל אני לא חושב שזה מאכזב עד כדי כך. במכונת טיורינג משתמשים כדי למצוא את ההבדלים בין דברים שב-P ובין דברים שב-NP, למשל, לא כדי לראות איך אופטימיזציות יכולות לאפשר לנו לחשב את RSA יותר מהר. ניתוח סיבוכיות של אלגוריתמים שניתנים לפתרון יעיל ממילא מבוסס לרוב על בחירה של פעולה מסויימת בתור "הפעולה הבסיסית" שאותה סופרים, לא על ספירת הצעדים שמכונת טיורינג עושה.
  כמה תווים נקראים? • גדי אלכסנדרוביץ'
  כמה תווים נקראים? • שוטה הכפר הגלובלי
  כמה תווים נקראים? • kozmo5449@gmail.com
  כמה תווים נקראים? • ab
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • ab
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • צפריר כהן • 2 תגובות בפתיל
  כמה תווים נקראים? • ab
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • עומר
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • עומר
  כמה תווים נקראים? • שוטה הכפר הגלובלי
  כמה תווים נקראים? • ידידיה • 2 תגובות בפתיל
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • עומר • 36 תגובות בפתיל
  כמה תווים נקראים? • ירדן ניר-בוכבינדר
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז • 4 תגובות בפתיל
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה • 5 תגובות בפתיל
  כמה תווים נקראים? • האייל האלמוני
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • האייל האלמוני
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • האייל האלמוני
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • האייל האלמוני
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • שוטה הכפר הגלובלי
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • אריק
  כמה תווים נקראים? • ידידיה • 38 תגובות בפתיל
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • אריק
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • אריק
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • אריק
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • אריק
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • easy
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • הפונז
  חרמפף • אריק • 3 תגובות בפתיל
  כמה תווים נקראים? • האלמון האיילי • 2 תגובות בפתיל
  כמה תווים נקראים? • ירדן ניר-בוכבינדר • 3 תגובות בפתיל
  כמה תווים נקראים? • שוטה הכפר הגלובלי • 2 תגובות בפתיל
  כמה תווים נקראים? • עומר • 7 תגובות בפתיל
  כמה תווים נקראים? • שוטה הכפר הגלובלי • 2 תגובות בפתיל
  כמה תווים נקראים? • שוטה הכפר הגלובלי
  כמה תווים נקראים? • צפריר כהן
  כמה תווים נקראים? • ידידיה
  כמה תווים נקראים? • שוטה הכפר הגלובלי
  כמה תווים נקראים? • עוזי ו. • 2 תגובות בפתיל

חזרה לעמוד הראשי

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