"כדי להשיג אקראיות במחשב משתמשים במספרים הנקראים פסאודו-אקראיים, הנחשבים אקראיים לכל שימוש מעשי אך הם למעשה סדרה דטרמיניסטית של מספרים" - לא מדויק. כדי להשיג אקראיות במחשב משתמשים במספרים פסאודו אקראיים, אך גם בגורמים שהדטרמיניזם שלהם אינו "פנימי" למחשב ואינו תלוי באלגוריתם זה או אחר, דוגמת השעון הפנימי של המחשב, קצב ההקשות והזזות העכבר של המשתמש וכו'. זו נקודה חשובה שהכרחי לפרט אותה (כרגע הערך לא נותן שום הסבר לאופן שבו בכל פעם שמקלידים "משחק חדש" בפריסל אכן מקבלים משחק שונה).
"אע"פ שכל בעיה אלגוריתמית פתירה, ניתנת לפתרון באמצעות אלגוריתם דטרמינסטי, בעבור חלק גדול מהבעיות האלגוריתמים הדטרמניסטיים איטיים יותר (במונחי סיבוכיות) ממשפחות אלגוריתמיות אחרות (כגון: אלגוריתמים לא דטרמינסטיים ואלגוריתמים הסתברותיים)." - גם פה צריך להיזהר. לא ידוע כיום האם הטענה הזו נכונה; ידוע רק שיש אלגוריתמים א"ד והסתברותיים שטובים יותר מהמקבילות הדטרמיניסטיות הקיימות שלהם; לא ידוע שזה בהכרח כך באופן עקרוני.
זה ממשיך ב-"קיימות מגוון של בעיות שימושיות... אשר לא ניתן לפתור אותן בזמן סביר" - צריך לשנות ל"אשר לא ידוע אם ניתן לפתור אותן בזמן סביר".
"למגוון של בעיות קיימים אלגוריתמים הפותרים אותן אך בעיות הקשורות אליהן אינן ניתנות לפתרון באמצעות אלגוריתמים דטרמיניסטיים." - זה אינו הרעיון החשוב כאן. מה שחשוב הוא קיומן של פונקציות מלכודת (Trapdoor), שניתנות להיפוך יעיל אם ידוע מידע נוסף, אך בלעדיו לא ברור אם הן ניתנות להיפוך יעיל.
"כיוון שקל יחסית לבדוק האם מספר הוא ראשוני או פריק, לא ניתן בזמן סביר לגלות מהם הגורמים המחלקים של מספר פריק." - המשפט הזה פשוט שגוי (כיוון שקל לבדוק אם מספר הוא ראשוני, נובע מכך שקשה לפרק אותו?). גם לא ברור מה מנסים להגיד כאן - הקלות של בדיקת ראשוניות (שהיא תוצאה חדשה וחשובה - למה לא לקשר פה ל-AKS או משהו?) אינה קשורה בכלל (לפחות כרגע) לבעיות שמסתמכות חלקית על הקושי של פירוק לגורמים, דוגמת בעיית RSA. אני מבין מה הרעיון הכללי שניסית לומר בחלק זה, אך הוא דורש שכתוב מהותי.
חבל שלא מזכירים בכלל מחלקות סיבוכיות כאן. לפחות את P כדאי להזכיר. אני מבין שאפשר לחשוש מ"הרתעה" של הדיוטות, אבל אפשר לשלב קצת העמקה בצורה לא מפחידה.
לא מוסבר בכלל בערך מה ההבדל בין אלגוריתם הסתברותי ואלגוריתם אי דטרמיניסטי - זה הבדל מהותי וחשוב, ומי שאינו מבין על מה מדובר יתבלבל כהוגן (להדיוט אין סיבה להניח ש"אי דטרמיניסטי" ו"הסתברותי" זה לא אותו הדבר; ההגדרה של אי דטרמיניזם היא די מוזרה ושרירותית עבור מתבונן מבחוץ).
אני מאוד קצר בזמן ולכן אגיב על מה שדורש ממני התייחסות מעטה, את כל השאר אשאיר למועד מאוחר יותר. לגבי 1 - למיטב ידיעתי הגורמים החיצוניים שאתה מדבר עליהם משמשים רק כ-Seed, הם אינם המספרים בהם משתמשים לצרכים אקראיים עצמם, המספרים האקראיים מתקבלים מהפעלת פונקציה (שהיא דטרמיניסטית מעצם ההגדרה של פונקציה) על אותו Seed שהוא אכן בד"כ אקראי, התוצאה המתקבלת היא מספר פסאודו-אקראי והמספרים שאתה מדבר עליהם הם רק חלק מהמנגנון. עם 2 ו-3 אני מסכים לחלוטין, כשכתבתי את זה חשבתי רק על צד אחד של המשוואה (ניוון של אלגוריתמים א"ד והסתברותיים לאלגוריתמים דטרמינסטיים) והזנחתי בשוגג את הצד השני (הידוע כ"P=NP?"). את 4 ו-5 אני צריך לקרוא בתוך ההקשר (מה שאני לא יכול לעשות כרגע). תרגיש חופשי לטפל ב-6 ו-8. המקום להתייחסות לבעיה 7 הוא בערכים המתאימים או בערך אלגוריתם. כפי שכבר כתבתי בדף השיחה שלי, מדובר בערך הראשון שעסקתי בו באופן רציני בוויקיפדיה ואיכותו כנראה בהתאם. תומר א. - שיחה19:57, 20 בספטמבר 2009 (IDT)[תגובה]
בקשר ל-1 אתה צודק, אבל כאמור - הערך לא מתייחס כרגע לנקודה הזו מספיק טוב. לא נכון להגיד ש"כדי להשיג אקראיות במחשב עושים כך וכך" בלי להזכיר חלק מהותי ואינטגרלי מהאופן שבו משיגים אקראיות במחשב. בקשר ל-7, ערך צריך לעמוד ככל הניתן בפני עצמו ובטח שלא לשגע את הקורא, וכרגע זה מה שהערך עושה, ולכן כדי לנסות ולפרט עוד טיפה, או להמנע מהכנסת אלגוריתמים אי דטרמיניסטיים לתמונה (ממילא לא מדובר במודל מעשי). בקשר ליתר - אני מעדיף שקודם כל תסיים לעשות עם הערך את כל מה שאתה רוצה/יכול ורק אז שאתחיל לגעת בו בעצמי אם עוד יהיה בכך צורך. עייפתי ממלחמות. גדי אלכסנדרוביץ' - שיחה21:59, 20 בספטמבר 2009 (IDT)[תגובה]
אני עשיתי את שלי (טיפלתי ב1, 2,3,5, 6) ב-4 אני לא יודע איך לטפל וב-8 אני לא אצליח לטפל. לגבי 7, הורדתי את ההתייחסות (למרות שאני חושב שהיא במקום). אתה מוזמן לעשות בערך כרצונך. תומר א. - שיחה13:24, 3 באוקטובר 2009 (IST)[תגובה]
ערכתי קצת. לטעמי עדיין יש בעיה מהותית מאוד בערך - הוא מניח שוב ושוב שכל המחשבים הם דטרמיניסטיים, ולכן קורים דברים רעים (אפשר לנחש את הקלפים במשחק/יש בעיות שאי אפשר לפתור וכו'). העניין הוא שבפועל מחשבים יכולים להשתמש באקראיות ועושים את זה כל הזמן. היא לא מושלמת, אבל היא עובדת מצויין בפועל. לראיה - במשחקי קלפים לא קל לרמות, ואלגוריתם מילר-רבין משרת אותנו מצויין. חייבים להתייחס לנקודות הללו איכשהו. גדי אלכסנדרוביץ' - שיחה14:22, 4 באוקטובר 2009 (IST)[תגובה]
המחשבים עצמם הם דטרמיניסטים, כל השיטות ליצירת מספרים אקראיים באמת הן חיצוניות למחשב (והיה אפשר לייצר את אותם מספרים על דף נייר באותה מידה). בכל מקרה, כל עניין האקראיות הזה יצא מפרופורציה ואולי כדאי להסיר אותו בכלל מהערך, זה הגיע יחד עם התרגום מהערך האנגלי ויתכן שזה לא נחוץ. תומר א. - שיחה19:31, 4 באוקטובר 2009 (IST)[תגובה]
שוב, מה זה "חיצוני למחשב"? אם המחשב משתמש ברעשים שהמעבד שלו משמיע כדי לייצר אקראיות, זה "חיצוני למחשב"? זו טענה פילוסופית מדי, וערכים כאלו לא צריכים לעסוק בפילוסופיה אלא בעובדות. אני חושב שאם מישהו יקרא את הערך, ואז מישהו יספר לו על מילר-רבין והוא יגיד "עזוב אותי משטויות, קראתי בויקיפדיה שאי אפשר עם מחשבים להשיג שיפורי זמן ריצה באמצעות אלגוריתמים אקראיים, כי מחשבים הם דטרמיניסטיים" הוא יביך את עצמו, וחבל. גדי אלכסנדרוביץ' - שיחה20:14, 4 באוקטובר 2009 (IST)[תגובה]
אבל שמע, מילר-רבין כן עובד אחלה בפועל (הרבה יותר טוב מ-AKS). איך זה אפשרי, אם אין שום דבר אקראי במחשב?
הנה ציטוט מויקי האנגלית, בערך העוסק ב-BPP: "BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines, by the method described above. For this reason it is of great practical interest which problems and classes of problems are inside BPP.". אם גם זה טרם משכנע אותך שאלגוריתמים הסתברותיים הם דבר קיים ורלוונטי למחשבים אמיתיים, אשמח לדעת איזה עוד שכנוע אתה רוצה. גדי אלכסנדרוביץ' - שיחה22:55, 4 באוקטובר 2009 (IST)[תגובה]
אני מתנצל על העיכוב, לא הייתי כאן כמה ימים. רק עכשיו הבנתי את מהות הדיון ביננו, אנסה לתמצת את עמדתי. ראשית, אינני טוען כלל שאלוגריתמים הסתברותיים אינם קיימים, הם קיימים ויעילים. שנית, המחשב אינו הקופסה שנמצאת מתחת לשולחן שלך אלא מודל מופשט שמורכב מיחידת עיבוד וזכרון והתקני קלט ופלט. למעשה, המחשב הוא איזושהי רדוקציה ממכונת טיורינג. זאת הסיבה שמדעי המחשב אינם עוסקים במחשבים (וגם לא בטלסקופים). הרעש שיוצר המעבד (מימוש ספציפי של מחשב) שנמצא אצלך בבית אינו חלק אינהרנטי למודל המחשב ולא תמצא רעש כזה במכונת טיורינג, למעשה, לא תמצא שום דבר אקראי במכונת טיורינג ולכן כל הSEED-ים האקראיים הם חיצוניים למחשב (קשורים למימוש הספציפי שלך). המחשב צריך שתכניס לו מספר אקראי כלשהו כקלט ולאחר מכן הוא יכול לבצע סדרת פעולות דטרמניסטית לגמרי כדי להפיק פלט פסאודו-אקראי. יחד עם זאת, כל העריכות האחרונות שלך בערך מקובלות עלי. תומר א. - שיחה14:06, 8 באוקטובר 2009 (IST)[תגובה]
אני לא בטוח שאני מבין את הכוונה של "רדוקציה ממכונת טיורינג", אבל כדאי לזכור שקיימות גם מכונות טיורינג הסתברותיות (זה המודל שבבסיס מחלקות כמו BPP). ובאופן כללי שאין בעיה עם מודלים שמניחים שמשהו "מגיע מבחוץ" (מכונות שמקבלות הוכחה, בהגדרה האלטרנטיבית של NP; מכונות שמקבלות "עצה", עבור מחלקות כמו P/poly). אני שמח לראות שלמרות אי ההסכמה ה"פילוסופית" שלנו קיבלנו תוצאה סופית ששנינו מרוצים ממנה. גדי אלכסנדרוביץ' - שיחה17:31, 8 באוקטובר 2009 (IST)[תגובה]
