שאלות ותשובות – מקבץ מס’ 1

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

אז מה זה בעצם אי דטרמיניזם? קשה להחליט

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

על הבעיה המסובכת של מציאת מחט בערימת שחת

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

מכונת טיורינג, 2: הנקמה (המסובכת)

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

למה גם מה שפתיר לא פתיר (זה מסובך)

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