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

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

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

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

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

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

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

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

אז מהי PSPACE?

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