סודרים – התיאור הפורמלי

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

סודרים – מה זה בכלל? (הסבר אינטואיטיבי תוך כדי משחק)

בפוסט הקודם דיברתי על האופן שבו קנטור "המציא" את הסודרים, אך כפי שיתברר בפוסט הזה, כנראה שהמילה "תגלית" יותר הולמת. קנטור הגיע אל הסודרים על ידי כך שהוא הגדיר סדרת קבוצות $latex P^{\left(1\right)},P^{\left(2\right)},\dots$ ושם לב שיש משמעות גם לקבוצה $latex … להמשיך לקרוא

איך קנטור המציא את הסודרים?

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

משפט רייס – הגרסה המלאה

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

IP=PSPACE – ההוכחה (חלק ב')

בפוסט הקודם שעסק בהוכחה ש-$latex \mbox{IP}=\mbox{PSPACE}$ הראיתי מערכת הוכחה אינטראקטיבית עבור השפה $latex \overline{3\mbox{SAT}}$. זו הייתה הדוגמה הראשונה למערכת הוכחה "רצינית", כזו שמשתמשת בכל הכוח של האינטראקטיביות; במערכות האחרות שהראיתי תוך סיבוב או שניים המשחק נגמר, ואילו כאן ההוכחה הייתה … להמשיך לקרוא

מדוע "הקנון המדעי" לא כולל מתמטיקה?

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

IP=PSPACE – ההוכחה (חלק א')

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

מה האסוציאציה שלכם ל-?=(1+2)2÷6?

מהומה בפייסבוק. מישהו פתח סקר עם השאלה הפשוטה: $latex 6\div 2(1+2)=? $ ושתי תשובות אפשריות – 1 ו-9. התוצאה? כרגע יש בסביבות ה-1,300,000 מצביעים עבור 1, 1,700,000 מצביעים עבור 9 ודיון בן למעלה מ-100,000 תגובות. מה לעזאזל? חשבתי להתעלם מזה … להמשיך לקרוא