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

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

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

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

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

בפעם הקודמת ניסחתי את כלל ה-0-1, ולכן עכשיו אגש להוכחה שלו בלי שהיות. הרעיון הבסיסי בהוכחה הוא פשוט מאוד, אבל גם מקסים: הבה ונתבונן בתורה $latex T$, שהפסוקים שלה הם בדיוק אותם פסוקים שמתארים תכונות $latex \mathcal{P}$ עם הסתברות 1. … להמשיך לקרוא

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

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