בתשובה לגדי אלכסנדרוביץ', 05/12/06 12:51
השפעת קרני השמש על קרני התיש 423143
שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ' יום ג', 5/12/2006, 13:47
לך ולירדן: תודה.

אני מניח שההגדרה שאני מכיר "A finite set of well-defined rules for the solution of a problem in a finite number of steps" אינה ההגדרה המקובלת. בסדר, נא לראות את ההערה בסוגריים כמבוטלת.
השפעת קרני השמש על קרני התיש 423147
האייל האלמוני • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 13:52
וויקיפדיה איתך "אלגוריתם הוא דרך שיטתית (כלומר כזו שצעדיה מוגדרים היטב) לביצועה של משימה מסוימת *במספר סופי של צעדים.*" http://he.wikipedia.org/wiki/%D7%90%D7%9C%D7%92%D7%9...
השפעת קרני השמש על קרני התיש 423157
גדי אלכסנדרוביץ' • בתשובה להאייל האלמוני יום ג', 5/12/2006, 14:18
מה שמבדיל את ויקיפדיה מויקימילון הוא שאפשר לפרט גם בפסקאות שבאות אחרי ההגדרה.
השפעת קרני השמש על קרני התיש 423160
שוטה הכפר הגלובלי • בתשובה להאייל האלמוני יום ג', 5/12/2006, 14:28
תודה. האמת היא, כמובן, שזה לא ממש חשוב לעצם העניין.

(ניחוש לגבי ההמשך:

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

- אני אבקש הסבר מהם צעדים שאינם מוגדרים היטב.

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

- אני אגיד שצעד שמוגדר היטב הוא צעד שהתוצאה שלו נקבעת באופן חד-משמעי.

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

- אני אטען שאם כך, התוצאה שלו נקבעת באופן אקראי או ע"י אלגוריתם כלשהו.

- יגידו לי "מה פתאום"?

- אני אגיד שאינני מכיר דרך נוספת, ואבקש שיראו לי כזאת.

- ...

- השרת של האייל יקרוס, או השמש תכבה (לא ברור מה יקרה קודם).

)
הטעות שלך 423177
האייל האלמוני • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 15:32
זה שהשתמשת במילה ''אלגוריתם'' במקום במילה ''מנגנון''. יש אנשים שיכולים לחשוב שכשאתה אומר ''אלגוריתם'' (או כל מושג אחר שמזכיר להם מתמטיקה) אתה גורם להם לתגובה מוזרה שגורמת מהם להתעלם מכל מה שאתה כותב אחר כך.
הטעות שלך 423180
האייל האלמוני • בתשובה להאייל האלמוני יום ג', 5/12/2006, 15:35
סביר שיש אנשים כאלה. לא זה המקרה כאן.
השפעת קרני השמש על קרני התיש 423194
גדי אלכסנדרוביץ' • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 16:00
יש בעיה חמורה עם "צעד שהפעולה שלו מוגדרת באופן חד משמעי". קח למשל את בעית העצירה, שהוכח שלא ניתן לפתור עם מכונת טיורינג: בהינתן קלט לבעיית העצירה, הפלט האפשרי הוא או "כן" או "לא". לכן על פי גישתך, "צעד" שבו אומרים "כן" או אומרים "לא" הוא צעד לגיטימי.

כמובן שהוא לא לגיטימי, כי לא ברור איך אפשר *לדעת* אם צריך לומר כן או לא. מה שחשוב הוא לא שהתוצאה תהיה מוגדרת באופן חד משמעי (זה בכלל לא הכרחי) אלא ש*החישוב שמבוצע במהלך הצעד* יהיה ברור בצורה חד משמעית. זה אפשרי רק אם הצעד מאוד פשוט - למשל, "חשב את ערך התא א' ועוד ערך התא ב' ושים את התוצאה בתא ג"'.
השפעת קרני השמש על קרני התיש 423206
שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ' יום ג', 5/12/2006, 16:27
לדעתי הצעד באמת לגיטימי, אבל ייתכן שהאלגוריתם ייתן תוצאה שגויה. זה קורה הרבה גם למכונות וגם לאנשים.
השפעת קרני השמש על קרני התיש 423224
גדי אלכסנדרוביץ' • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 17:32
בניגוד לדרישה שהאלגוריתם יעצור, הדרישה לנכונות הרבה יותר נוקשה (אם כי גם עליה מוותרים באופן חלקי לפעמים), אבל זה עדיין לא רלוונטי. כדי שהצעד יתבצע, אתה צריך שיהיה ברור איך ניתן לבצע אותו.

צעד כמו ''בדוק האם התשובה הנכונה היא כן או לא'' הוא לא צעד שניתן לבצע בהקשר של בעיית העצירה. אתה כנראה חושב על צעד כמו ''הטל מטבע וענה ''כן'' אם יצא עץ'', שהוא כן נמנה על הצעדים ה''קלים לביצוע''.
השפעת קרני השמש על קרני התיש 423228
שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ' יום ג', 5/12/2006, 17:54
אני חשבתי על הצעד "ענה "כן"".

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

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

אם אתה מרגיש שהתשובה היא "כן", ענה "כן". אחרת, ענה "לא".
השפעת קרני השמש על קרני התיש 423231
גדי אלכסנדרוביץ' • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 18:05
הצעד הזה הופך אלגוריתמים לחסר כל ערך. באופן כללי, גם כשיש לך אלגוריתם הסתברותי, דרישה בסיסית ממנו היא שעל *כל* קלט יתן תשובה נכונה בהסתברות חיובית, אחרת מה הטעם בו? אלגוריתם נהדר לבדיקת ראשוניות הוא "ענה כי המספר לא ראשוני". הרי רוב המספרים לא ראשוניים, אז רוב הזמן האלגוריתם צודק. הבעיה היא שיש קלטים שעליהם האלגוריתם *תמיד* טועה.

אחרי שנתתי את הנאום הזה (ולא נעים למחוק) שמתי לב שאתה לא מדבר על אלגוריתמים אלא על שמלגוריתמים. מכיוון שבני אדם לא צריכים אלגוריתמים (=פתרונות לבעיות) אלא שמלגוריתמים (=מישהו שיגיד להם מה לעשות, גם אם הם עושים טעות), אני נוטה להסכים שאין כאן בעיה.
השפעת קרני השמש על קרני התיש 423156
גדי אלכסנדרוביץ' • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 14:17
יש הרבה הגדרות מקובלות לאלגוריתמים. דרישת עצירה היא דרישה סבירה מרוב האלגוריתמים הבסיסיים (קבל קלט-בצע עליו חישוב כלשהו-החזר את תוצאת החישוב). ההגדרה הכללית יותר של אלגוריתם היא ''משהו שמכונת טיורינג עושה'', ואז הוא לא חייב לעצור.
השפעת קרני השמש על קרני התיש 423184
שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ' יום ג', 5/12/2006, 15:41
בההגדרה הזאת אני ממש לא רוצה להשתמש, כי היא *באמת* הופכת את הטיעון שלי למעגלי: אם האדם הוא מכונת טיורינג, ברור שאין לו בחירה חופשית.
השפעת קרני השמש על קרני התיש 423199
גדי אלכסנדרוביץ' • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 16:06
זו בעיה משמעותית, כי אז אתה באמת צריך למצוא הגדרה טובה *מאוד* לאלגוריתם - בפרט הגדרה כזו שתהיה כללית יותר מזו של מכונת טיורינג. כלומר, אתה צריך להגדיר אלגוריתם בתור משהו שייתכן שמכונת טיורינג לא יכולה לעשות - ובכך להגיד שהתזה של צ'רץ' וטיורינג לא נכונה. בהצלחה עם זה. לחילופין, אולי עדיף לא להשתמש במילה "אלגוריתם".
השפעת קרני השמש על קרני התיש 423207
שוטה הכפר הגלובלי • בתשובה לגדי אלכסנדרוביץ' יום ג', 5/12/2006, 16:28
כן, אני הולך ומגיע למסקנה שהמילה הזאת מפריעה יותר משהיא עוזרת כאן. הבה נשכח ממנה.
השפעת קרני השמש על קרני התיש 423279
ירדן ניר-בוכבינדר • בתשובה לשוטה הכפר הגלובלי יום ג', 5/12/2006, 23:20
יכול להיות שהתבלבלתי בין אלגוריתם לבין חישוב, או מכונת טיורינג. מבחינתי, ההערה בסוגריים יכולה לחזור לתוקף. כמובן, זה לא משנה.
חזרה לעמוד הראשי
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות