בתשובה לעדי סתיו, 08/01/07 15:01
כמה תווים נקראים? 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
מ"ט=מכונת-טיורינג

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

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