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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

השארת הרצף

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

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

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

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

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

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

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

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

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

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

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