חידת צפרדע

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

הוכחת בעיית העצירה – המכונה הזדונית נגד אליהו הנביא (ואיך זה קשור לפרדוקס ניוקומב ולתוכנות שמדפיסות את הקוד של עצמן)

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

בעיית העצירה (אני מסרב לתת כאן שם מתחכם)

בפוסטים האחרונים דיברנו על מכונת טיורינג. מכונת טיורינג היא מעין מחשב זעיר, שמקבל כקלט סדרה של אפסים ואחדים, "רץ" עליהם (מבצע כל מני פעולות חישוב), ובסופו של דבר עוצר ואומר "כן" או "לא". אחלה. אלא שבשום מקום לא נדרש שהמכונה אכן תעצור. קל מאוד לכתוב מכונה שאינה עוצרת. הנה: מכונה בעלת מצב אחד, $latex q_0$, …

עוד מכונות מופלאות

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

המכונה המופלאה

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

על תורה העומדת על כריעות תרנגולת

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

אל R מ-RE: מניה רקורסיבית באינסוף צעדים

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

אלגוריתם סופי דטרמיניסטי (או: מה זה בכלל?)

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

על משוואות דיופנטיות ושאר בעיות שהשוליים הללו צרים מלהכיל

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

על נמלים, נזירים ומסלולים צרים

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

המגדל הלוהט 2: הנקמה

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

המגדל הלוהט

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

על מתמטיקאים קולנועיים מטורפים ו-216 הספרות של "פאי"

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