פוסט של בעיית ההתאמה של פוסט

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

הבעיה העשירית של הילברט – פונקציות דיופנטיות וחיות אחרות (רקורסיביות)

אנו ממשיכים בדרך שלנו אל ההוכחה שלא קיים אלגוריתם שפותר את הבעיה העשירית של הילברט. אני מניח שקראתם את פוסט המבוא ולכן קופץ ישר לעניינים הפעם. המושג המרכזי בפוסט הקודם היה קבוצה דיופנטית. זוהי קבוצה $latex S=\left\{ \left(a_{1},\dots,a_{n}\right)\right\} $ של … להמשיך לקרוא

הבעיה העשירית של הילברט – מבוא

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

יום הולדת 100 לאלן טיורינג!

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

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

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

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

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

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

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

אז מדוע קשה להוכיח ש-P שונה מ-NP? (בלכסון)

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

הפוסט שיודע להדפיס את עצמו

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

אז מה הקשר בין אוטומטים ופונקציות יוצרות?

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

אוטומטים סופיים ושפות רגולריות

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

משפט אי השלמות הראשון של גדל – איך (בערך) מוכיחים אותו?

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

הפוסט המעניין ביותר שלא ניתן לתאר בכותרת שלו

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

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

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

השארת הרצף

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

על הבעייה הלא טריוויאלית של זיהוי תכונה לא טריוויאלית

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

ומה הקשר של בעיית העצירה לאלכסון של קנטור?

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

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

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

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

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

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

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