זוג או פרד (כן, עם ד’!)

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

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

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

כלל ה-0-1 של גרפים – ההוכחה

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. למשל, הפסוק $latex \exists v_{1},v_{2},v_{3}\left(E\left(v_{1},v_{2}\right)\wedge E\left(v_{2},v_{3}\right)\wedge E\left(v_{3},v_{1}\right)\right)$ שמתאר את "בגרף קיים משולש" שראינו בפוסט הקודם …

כלל ה-0-1 של גרפים – הקדמה

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