המותר האדם מן האלגוריתם, חלק 2 – הנקמה?

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

המותר האדם מן האלגוריתם?

אחד מהספרים שאני נאבק איתם בקביעות עוד מתחילת הלימודים שלי באוניברסיטה הוא The Emperor's New Mind ("תודעת המלך החדשה"? על משקל "בגדי המלך החדשים") של רוג'ר פנרוז. בפשטות, הספר מתעסק באחת השאלות הפילוסופיות המרתקות ביותר שאני, כאדם המתעניין במדעי המחשב, יכול להעלות על הדעת – האם התודעה האנושית היא בסך הכל אלגוריתם שרץ על מחשב …

הוכחה לא קונסטרוקטיבית לכך שרציונלי זה טרנסצנדנטי (טוב, לא בדיוק…)

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

התופעה החשבונית המסתורית של שנת 2011 (היא שהטמטום של חדשות 2 הוא אינסופי)

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

אז מהי PSPACE?

שני המשאבים המרכזיים שמדברים עליהם בתורת הסיבוכיות הם זמן וזכרון. בכל הנוגע לזמן, הפורמליסטיקה בוחרת להגדיר "זמן יעיל" כזמן שהוא פולינומי בגודל הקלט של האלגוריתם – כלומר, אם $latex x$ הוא הקלט וב-$latex \left|x\right|$ אנחנו מסמנים את אורכו (מספר הביטים שמקודדים אותו), אז אלגוריתם הוא "יעיל" בכל הנוגע לזמן הריצה אם קיים פולינום $latex p$ …