בתשובה לגדי אלכסנדרוביץ', 08/01/07 13:43
 |
|
 |
||
|
||||
 |
הכלי, מכונת הטורינג שבעזרתה משתמשים כדי למדוד סיבוכיות, הוא כלי שונה מהכלי מכונת הטורינג שבעזרתה משתמשים כדי לבדוק בעיות כריעות. הראשון מכיל בתוכו את השני, ואת הנחת הזמנים. |  |
 |
 |
|
|
|
||
|
||||
|
נראה לי שאתה קצת נסחף. זו בדיוק אותה מכונה (כלומר, אותו מודל). ההבדל הוא רק בצורה שבה מגדירים באמצעותה מחלקות סיבוכיות. בתור R מסמנים את כל השפות שניתנות להכרעה על ידי מכונת טיורינג (שלא טורחים לספור את הצעדים שלה), ובתור P מסמנים את כל השפות שניתנות להכרעה על ידי אותו סוג של מכונת טיורינג, רק שהפעם בודקים שמספר הצעדים שהיא מבצעת לא גדול יותר מפולינום נתון של גודל הקלט. יש המון סוגים אחרים של מכונות שונות: אביב ציין כאן את המכונה האי דטרמיניסטית, ויש גם מכונה הסתברותית, ומכונה קוואנטים וכדומה. המודלים הללו מגדירים מחלקות סיבוכיות שונות, ואז עולה השאלה מה הקשרים בין המחלקות הללו. למשל, השאלה האם P=NP היא השאלה האם חישוב יעיל במכונה דטרמיניסטית שקול לחישוב יעיל במכונה אי דטרמיניסטית (ומאמינים שהתשובה היא שלילית, כלומר יש הבדל מהותי בין שני המודלים הללו *מבחינת זמן החישוב*, וזאת למרות שמודדים את זמן החישוב באותה הצורה בדיוק - ספירת צעדים). אם לא היינו מגדירים חישוב יעיל בתור P אלא, נניח, בתור כל השפות שניתן לזהות במספר צעדים שהוא פולינום מדרגה שלוש של גודל הקלט, פתאום היינו מגלים שמחלקת השפות שמתקבלות בצורה יעילה על ידי מכונה חד-ראשית ומחלקת השפות שמתקבלות בצורה יעילה על ידי מכונה דו-ראשית הן (כנראה) שונות. כדי להימנע מזה הגדירו חישוב יעיל בתור פולינום כללי, לא מדרגה חסומה. |
|
|
|
|
|
|
||
|
||||
|
אני נסחף? נראה לי שאנחנו לא מדברים באותה שפה. הטענה שלי היא מאד פשוטה: ברגע שאתה רוצה לדבר על סיבוכיות (ושיהיה לדיבורים על סיבוכיות המשמעות המקובלת) אתה חייב להניח הנחה על הזמן שלוקח לפעולה. כל זמן שאתה מדבר על כריעות, ולא על סיבוכיות אין בהנחה כזאת שום תועלת. בסופו של דבר, זאת טענה ממש טריויאלית, מאד מוזר לי שהייתי צריך להוכיח אותה, עוד יותר מוזר לי שגם אתה, גם אביב וגם דורון לא מבינים אותה/לא מסכימים איתה, והכי מוזר לי שאחרי כל הדיון הזה היא עדיין נראית לך כמו "הסחפות". |
|
|
|
|
|
|
||
|
||||
|
אני תמיד חשבתי שבסיבוכיות משווים את מספר הפעולות הנדרשות כפונקציה של אורך הקלט, ושואלים על האסימפטוטיקה. כל עוד יש מספר סופי של סוגי פעולות והזמן הנדרש לכל פעולה כזאת הוא חסום, זה שקול לשאלות על האסימפטוטיקה של זמן הריצה, לא? | |
|
|
|
|
|
||
|
||||
|
הבנתי שזה גם מה שגדי אומר, לא? | |
|
|
|
|
|
||
|
||||
|
לא יודע (מתברר שאנחנו לא ממש מבינים אחד את השני, אז אני האחרון שיכול להיות הפרשן שלו). | |
|
|
|
|
|
||
|
||||
|
במשמעות המקובלת של סיבוכיות, הסיבוכיות של חישוב אחד שווה לסיבוכיות של חישוב שני אם הזמן של החישוב השני הוא לכל היותר מכפלה קבועה של הזמן של החישוב הראשון, ולהפך. אז אם ''הזמן שלוקח לפעולה'' של מכונה אחת הוא לכל היותר מכפלה קבועה של ''הזמן שלוקח לפעולה'' של מכונה אחרת, אז אין ל''זמן שלוקח לפעולה'' כל השפעה על הסיבוכיות. | |
|
|
|
|
|
||
|
||||
|
ובשפה שאני מדבר בה, הפסוקית שבאה בין ''אם'' ל''אז'' במשפט השני שלך היא ''הנחה''. | |
|
|
|
|
|
||
|
||||
|
תראה, בתחום הזה מודדים את הזמן בפעולות של מכונת-טיורינג. השאלה כמה זמן לוקחת פעולה אחת יכולה להיות רלבנטית רק כשמסמלצים מכונה אחת באמצעות אחרת, כי אז מודדים את הזמן בפעולות של המכונה הבסיסית יותר. | |
|
|
|
|
|
||
|
||||
|
את ההנחה שהזמן שלוקחת פעולה אחת הוא קבוע/ חסום/ בעל התפלגות ידועה מראש ומתנהגת יפה חייבים להניח כי אחרת אין למספר הפעולות של מכונת הטיורינג שום משמעות (אבל, כששואלים אם המספר הוא סופי או לא חייבים רק להניח שהזמן שלוקחת פעולה הוא סופי). | |
|
|
|
|
|
||
|
||||
|
אולי אני מבין מאיפה חוסר ההסכמה. מה שמפריע לך הוא ש"מדידת זמן" במכונת טיורינג היא בעצם ספירת צעדי חישוב, ולא מדידה של זמן אמיתי? ("צעד חישוב" במכונת טיורינג - מעבר ממצב פנימי אחד למצב אחר, כתיבה של תו על הסרט והזזת הראש ימינה או שמאלה, בהתאם למצב הקיים ולתוכן הסרט שהראש הקורא קורא). |
|
|
|
|
|
|
||
|
||||
|
ממש לא. אני כותב את מה שאני חושב, בעברית הכי פשוטה שיש. למה אתה חושב שאני משקר? | |
|
|
|
|
|
||
|
||||
|
אני לא חושב שאתה משקר, אני פשוט לא מבין מה אתה מנסה לומר. אם אנחנו סופרים צעדים במכונת טיורינג, מה אכפת לנו כמה זמן "אמיתי" הם לוקחים? | |
|
|
|
|
|
||
|
||||
|
לספור את מספר הצעדים? 14,123 צעדים. ספרתי, מה עכשיו? אין למספר הזה שום משמעות בשום מודל שאני מכיר. מה איכפת לך הזמן האמיתי, אתה זה שנתן דוגמאות מעולם על מיון של מחשבים, לא? |
|
|
|
|
|
|
||
|
||||
|
הרעיון הוא לספור את מספר הצעדים כפונקציה של גודל הקלט, ולבדוק איזו פונקציה קיבלנו. זה ילמד אותנו משהו על ההתנהגות של האלגוריתם שהמכונה מייצגת גם במחשבים ''אמיתיים'', למרות שזה לא יכול להגיד לנו כמה זמן זה ייקח עבור גדלים ספציפיים. | |
|
|
|
|
|
||
|
||||
|
זהו, שזה ילמד אותנו משהו על ההתנהגות של האלגוריתם שהמכונה מייצגת גם במחשבים "אמיתיים" *רק תחת הנחה כלשהיא על הזמן של ביצוע הפעולה*. בלי זה נשארת עם סתם מספר, פונקציה או אסימפטוטה שלא מלמדת אותך כלום על כלום. | |
|
|
|
|
|
||
|
||||
|
לדעתי האסימפטוטיקה אומרת לנו משהו גם בלי ההנחות שאתה מציין - היא מאפשרת לנו *להשוות* בין שני אלגוריתמים שונים (אלגוריתם מהיר יותר = אלגוריתם שהפונקציה שלו גדלה יותר לאט אסימפטוטית). אם לדעתך זה לא אומר כלום - לא נורא. לא צריך להמשיך את הדיון, ואיש בדעתו יחיה. |
|
|
|
|
|
|
||
|
||||
|
באמת אין שום משמעות. זה מודל. אין משמעות לעצם השאלה ''הזמן שלוקחת פעולה'', כי ''פעולה אחת'' היא יחידת הזמן שלנו מלכתחילה. אם תגדיר אותה בשניות, עדיין תצטרך להגדיר שנייה, ולהסביר למה שנייה של מ''ט אחרת שווה לשנייה של מ''ט אחרת (ולא, נאמר, שאחת נייחת ביחס אלינו והשנייה משייטת במהירות קרובה למהירות האור, או השד יודע מה). | |
|
|
|
|
|
||
|
||||
|
אם אתה לוקח את מכונת טיורינג בתור מודל שאין בו משמעות לזמנים, אז ברגע שהצלחת לסמלץ מכונה אחת בעזרת אחרת, שתי המכונות זהות. אם אתה מייחס משמעות לזמנים, אתה חייב להניח משהו לגבי הזמנים (וגם ההנחה ש''פעולה אחת'' היא יחידת הזמן שלך היא הנחה). אי אפשר לאכול את העוגה ולהשאיר אותה שלמה. | |
|
|
|
|
|
||
|
||||
|
אין משמעות ל"זמנים", אבל יש משמעות למספר צעדי החישוב. אם חישוב במודל אחד לוקח פי n יותר צעדים מאשר במודל השני, אי אפשר להגיד ששני המודלים זהים, ואפילו לא שאפשר להתעלם מההבדל ביניהם. | |
|
|
|
|
|
||
|
||||
|
רגע, עכשיו יש לי מודל חדש, שעושה שני צעדים במקום כל צעד של המודל הקודם, ז"א ספרתי את הצעדים ויצא לי 28,246. לא תרשה לי להתעלם מההבדל ביניהם? | |
|
|
|
|
|
||
|
||||
|
בוא נתכנס לתגובה 428361. | |
|
|
|
|
|
||
|
||||
|
''זמן'' במכונת-טיורינג מוגדר כ''מספר הפעולות שהמכונה ביצעה''. זו לא הנחה, זו הגדרה. (ויש לה משמעות לא יותר ולא פחות מלכל הגדרה.) | |
|
|
|
|
|
||
|
||||
|
וכשאנחנו רוצים להסיק מסקנות מהמודל לעולם האמיתי (כמו שניסו להעשות בתחילת הפתיל) צריך לתת משמעות בעולם האמיתי לזמן במכונת טיורינג (או להתעלם מהמושג). | |
|
|
|
|
|
||
|
||||
|
אה, לשם אתה חותר? בסדר, אני מסכים. | |
|
|
|
|
|
||
|
||||
|
בעולם האמיתי זו לא בעיה. קשה לי אפילו לדמיין מכונה פיסית שמסמלצת מ''ט בצורה כזו שכל צעד מ''ט לוקח זמן אקספוננציאלי באורך הקלט. לכן מ''ט זה מודל כל-כך שימושי בניגוד למודלים שקולים אחרים. | |
|
|
|
|
|
||
|
||||
|
בעולם האמיתי זה לא בעיה בגלל שמניחים הנחות לגבי הזמן של כל פעולה. ללא הנחות, המודל היה פשוט לא שימושי. | |
|
|
|
|
|
||
|
||||
|
לא-לא. אתה לא יכול להניח הנחות בעולם האמיתי. אתה יכול רק לקוות שהעולם תואם מספיק את המודל שלך. מסתבר שבכל/רוב מכונות החישוב שאנחנו בונים, זמן פיסי הוא באמת פרופורציונאלי פחות-או-יותר לזמן מ"ט. לכן מ"ט זה המודל הסטנדרטי למכונות חישוב ולא כל-מיני מודלים מופרעים שאני יכול להעלות על דעתי. | |
|
|
|
|
|
||
|
||||
|
ה"היסחפות", לטעמי, היא שאתה אומר שאם סופרים מספר צעדים של משהו, הוא הופך להיות משהו אחר. נניח שיש לי מכונית ושמד סיבובי המנוע בתוכה מכוסה בסלוטייפ. עכשיו בוא נניח שאני מוריד את הסלוטייפ. האם קיבלתי מכונית שונה? |
|
|
|
|
|
|
||
|
||||
|
זה1 לא מה שאמרתי (וחוץ מזה, נראה לי שממש לא הבנתי את המשל שלך). 1 מה שאמרתי הוא שאם יש הנחות נוספות על מושג מתמטי אז כבר מדובר על מושג אחר, שמכיל בתוכו את המושג הקודם. למשל, חבורה שהמכפלה שלה היא הופכית היא חבורה אבלית. חבורה אבלית היא חבורה, אבל חבורה היא לא בהכרח חבורה אבלית.2 2 ואני משוכנע שאתה יודע את זה. הרי אתה מככב ב http://he.wikipedia.org/w/index.php?title=%D7%97%D7%... |
|
|
|
|
|
|
||
|
||||
|
אוקיי. מה ההנחה הנוספת שיש על המכונה במקרה הזה? כזכור, אין שום הנחות לגבי הזמן שלוקח למכונה לבצע צעד חישוב. | |
|
|
|
|
|
||
|
||||
|
לא יודע, "מניחים שכל צעד שמכונת הטיורינג עושה לוקח יחידת זמן אחת" זה לא הנחה (תגובה 428292)? | |
|
|
|
|
|
||
|
||||
|
לא, זו הגדרה. אתה יכול לסלק את ה''מניחים'' אם הוא מפריע לך ולהחליף את המשפט ב''מגדירים את יחידת הזמן הבסיסית שלנו בתור צעד של המכונה'' (שזה מה שהתכוונתי לומר). | |
|
|
|
|
|
||
|
||||
|
האם מה שמפריע לך היא ההנחה שהזמן (ב"עולם האמיתי" יהא אשר יהא) שלוקח לבצע פעולה הוא קבוע (או חסום ע"י קבוע)? אולי זו ההנחה שכולם בדיון מניחים כמובנית מאליה, חוץ ממך? | |
|
|
|
|
|
||
|
||||
|
כן, קבוע, חסום על ידי קבוע, מתפלג יפה, משהו. ברור לי שכולם כאן מניחים את זה כמובן מאליו, לא ברור לי למה, ולמה הם מתעקשים שהם לא. | |
|
|
|
|
|
||
|
||||
|
לא נראה לי שמישהו התעקש שהוא לא מניח את זה, אלא שלא ברור למה זה רלוונטי לדיון - בפרט, למה זה משנה את המודל של מכונת הטיורינג ולמה זה חשוב רק כשמודדים סיבוכיות זמן ולא בודקים כריעות. הרי אם פעולה בסיסית במכונת טיורינג עלולה לקחת אינסוף זמן בעולם האמיתי, זה חשוב גם לשאלות של כריעות. | |
|
|
|
|
|
||
|
||||
|
אני לא יודע על מה ולמה התעקשתם. אני יודע *בדיוק* על מה ולמה אני התעקשתי, הסברתי משהו שהוא פשוט (ממש פשוט) ונכון (ממש נכון), ניסחתי את זה בשש צורות שונות. נימקתי. הוכחתי. הדגמתי. הסברתי. חזרתי והסברתי. אתם התעקשתם, מסיבה שעד רגע זה לא ברורה לי, מנימוקים ששייכים לדיון אחר לגמרי, לתקן אותי. הייתי מציע לכם בפעם הבאה לנסות ולהבין את מה בדיוק אתם מתקנים לפני שתתקנו (ולגבי עצמי, הייתי מציע לעצמי לא לכתוב יותר שום דבר "מקורי" באייל1. נראה לי שגם אם אני אכתוב ש 3+2 יוצא 5, מישהו יקפוץ ו"יתקן" אותי תוך כדי ציטוטים מההרצאה האחרונה במאקרוכלכלה או בספרות השוואתית שהוא נכח בה). כתבתי שבשביל לבדוק כריעות צריך להניח שזמן הפעולה הוא סופי. אני מקווה (לא שעל סמך הדיון הזה יש לתקוה על מה להסתמך) שההבדל ברור, ושאני לא צריך לנמק אותו. למה זה רלוונטי לדיון, אתה שואל ברצינות? הרי, כמו שהסברתי, ללא הנחה הזאת, כל הדיון שלכם על הוספת והורדת ראשים הוא דיון מיותר, ומכונה עם שני ראשים זהה לכל דבר ועניין למכונה עם ראש אחד. --------------- 1 כן, כולל התגובה הזאת. וכן, אני יודע, אם חמישה אנשים אינטליגנטיים ובלתי תלויים לא מבינים משהו, הבעיה היא של המסביר ולא שלהם. |
|
|
|
|
|
|
||
|
||||
|
ייתכן שחלק מהסיבה שבגללה לא מבינים את התגובות שלך היא שלא נעים לקרוא אותן. (הדיון על הורדת והוספת ראשים הוא מיותר בכל מקרה אם אנו עוסקים בכריעות. מה שאמרתי הוא שההבדל מעניין כאשר עוברים לעסוק בסיבוכיות.) |
|
|
|
|
|
|
||
|
||||
|
אני מבקש בכל לשון של בקשה לעצור את התדרדרות רגע אחד לפני שעוברים להסרת ראשים. | |
|
|
|
|
|
||
|
||||
|
ממש לא יפה לכתוב כך על סמיילי. הדבר האחרון שאתה יכול להגיד זה שלא נעים לקרא אותו כי הוא כותב בשפה נקיה בלי הצטעצויות ובדיחות קרש אתה יכול שלא לאהוב את סגנון ההתדינות הפרטני שלו אבל את זה היתה חייב לגלות לפני הדיון ולא בסוף | |
|
|
|
|
|
||
|
||||
|
תגובה 428319 מקובלת עליך? | |
|
|
|
|
|
||
|
||||
|
כן. הטענה שלי היא ש"פעולה" הוא מושג מורכב שמסוגל להחביא בתוכו דברים שתלויים בגודל הקלט. למשל, כשאתה כופל שני מספרים אתה בדרך כלל רואה את זה בתור "פעולה בסיסית" שהיא יחידת הספירה הקטנה ביותר. למרות זאת, כפל של שני מספרים למעשה תלוי באורך הייצוג שלהם. אם אנחנו כותבים אלגוריתם שיכול לקבל כל שני מספרים, צריך להתחשב בכך שככל שהמספרים גדולים יותר, כך הכפל שלהם ייקח יותר זמן. איך זה מתקשר למכונות הטיורינג החד-ראשית והדו-ראשית? בכך שאם מציגים אלגוריתם כלשהו שמשתמש ביכולות של המכונה הדו-ראשית, הרי שמה שנראה לנו כמו "פעולה בסיסית" במכונה הדו-ראשית עשוי לקחת זמן *שתלוי בגודל הקלט* במכונה החד-ראשית. |
|
|
|
|
|
|
||
|
||||
|
מעניין. אבל למעשה כשמדברים על "כפל" מדברים על כפל של X ביט או משהו כזה, לפחות מבחינה מימושית, ולכן מספר הפעולות עולה כשהקלט מתארך תגובה 193615. | |
|
|
|
|
|
||
|
||||
|
''מספר הפעולות עולה כשהקלט מתארך'' זה מה שאמרתי. | |
|
|
|
|
|
||
|
||||
|
ממש לא. כתבת שפעולה בסיסית תלויה באורך הקלט. לא שצריך יותר פעולות בסיסיות לטפל בקלט ארוך יותר. | |
|
|
|
|
|
||
|
||||
|
לא. כתבתי ש''פעולה'' (לא ''פעולה בסיסית'') היא מושג שיכול להחביא בתוכו פעולות בסיסיות יותר, ומכיוון שמספר הפעולות הזה עשוי לגדול עם אורך הקלט, ''פעולה'' באופן כללי יכולה להיות תלויה באורך הקלט. | |
|
|
|
|
|
||
|
||||
|
" כשאתה כופל שני מספרים אתה בדרך כלל רואה את זה בתור "פעולה בסיסית" שהיא יחידת הספירה הקטנה ביותר" ==> כפל היא פעולה בסיסית. "שככל שהמספרים גדולים יותר, כך הכפל שלהם ייקח יותר זמן." ==> כפל תלוי באורך הקלט. ומכאן - פעולות בסיסיות תלויות באורך הקלט. אבל מתוך התחשבות בשכ"ג בוא נפסיק עם זה. הרי גם אתה וגם סמיילי הסכמתם על תגובה 428319, אז על מה הויכוח, בעצם? |
|
|
|
|
|
|
||
|
||||
|
זה בכלל לא מפריע לי, רק רציתי לדעת באיזו מידה אני חריג מבחינת הפהקת שהנושא הזה מעורר בי. תמשיכו. | |
|
|
|
|
|
||
|
||||
|
ניסיתי להראות שמה שאנחנו קוראים לו ''פעולה בסיסית'' בטעות - ולכן המרכאות - יכול להיות מורכב מדברים יותר בסיסיים מתחת לפני השטח. אבל אתה צודק - אפשר לעזוב את זה וגם לי לא ברור על מה הויכוח, ואני לא מתפלא ששכ''ג מפהק. | |
|
|
|
|
|
||
|
||||
|
היה פעם הו-הה גדול ממעבדי RISC אצלם היה סט קטן של פעולות בסיסיות, אבל כל אחת מאלה התבצעה במהירות גבוהה מאד. בחמש עשרה דקות התהילה שלהם, מעבדים אלה נחשבו למבשרי העתיד. היום, דומני, עתידם בעברם. בגלל כל השאלות האלה היה מי שטען ש MIPS הוא ר"ת של Meaningless Index of Performance of Systems. |
|
|
|
|
|
|
||
|
||||
|
עתידם עמנו עדיין: מעבדים מודרניים הם למעשה ליבת RISC שמסמלצת מעבד וירטואלי. | |
|
|
|
|
|
||
|
||||
|
סליחה מראש על גסות הרוח: תמהני אם עוד מישהו בקהל מוצא את השאלות האלה לדבר המשעמם ביותר מאז "מלחמה ושלום". | |
|
|
|
|
|
||
|
||||
|
''מלחמה ושלום'' דווקא די מעניין כל עוד טולסטוי לא נגרר לדיונים על מהות ההיסטוריה. | |
|
|
|
|
|
||
|
||||
|
|
|
|
|
|
|
||
|
||||
|
האמת שדווקא קראתי עכשיו בעניין רב את כל הפתיל הזה. לא הבנתי כמעט כלום, אבל תמיד מצחיק לראות את סמיילי מתכתש עם אנשים חכמים שלא מבינים מה הוא רוצה. הקסם, כמובן, זה שמבחינה טכנית הוא תמיד צודק. | |
|
|
|
|
|
||
|
||||
|
לא כל מה שמשעמם הוא לא נכון. מעבדי risc כוחם הולך וגדל בימינו (ככל שאני מבין) ולדוגמא: מעבדי arm בניידים הם סוג של מעבדי risc וכן המעבדים בלוחות גרפיים הם סוג של מעבדי risc. המהירות הגדולה בחישובים פשוטים של מעבדים גרפיים מאפשרת להעזר בהם כאשר למהירות החישוב יש חשיבות גדולה , להלן שלוש דוגמאות: א. גרפיקה של משחקים, ב. כריה של מטבעות קריפטוגרפיים, ג. חישובים לצורך בניית תוכנות AI שמבוססות על סקירה של נתונים שכמותם "אסטרונומית". |
|
|
|
|
|
|
||
|
||||
|
המעבדים הגרפיים שונים ממעבדי RISC: יש להם המון ליבות חלשות יחסית ולכן הם יכולים לחשב במהירות רבה יותר חישובים שאפשר לחלק לחלקים קטנים ובלתי תלויים. | |
|
|
| חזרה לעמוד הראשי | המאמר המלא |
| מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים | |
 RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש
|
© כל הזכויות שמורות |