חידת צפרדע

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

המגדל הלוהט

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

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

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