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