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

החלטתי לפתוח במסורת חדשה. בין הנשמות התועות שמגיעות בטעות אל האתר הזה ישנן רבות שחיפשו ביטוי ספציפי מדוייק עד כדי כך שאוכל לנחש מה רצו. מכיוון שלרוב אין תשובה לשאלה שלהן בדף שאליו הגיעו, אנסה לענות על השאלות כאן, במקבצים. 1) "חבורה מסדר 6" – קיימות בדיוק שתיים כאלו. האחת היא $latex \mathbb{Z}_6$ – החבורה …

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

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

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

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

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

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

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

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