מפתח תשובות · יחידה 8

חישוביות.

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

קטלוג הטעויות הנפוצות

מפתח תשובות 4

שיעור 1 מתוך 4 · כ־20 דקות

מכונת טיורינג

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

לפתוח את השיעור

5 השלבים והתשובות שלהם

שלב 1 מתוך 5
לפתוח את השלב
קורא, כותב, זז
תרגול · בחרו
השאלה
מה מכונת טיורינג עושה בצעד אחד?

התשובה הנכונה
- נכונה קוראת את התא שמתחת לראש, כותבת בו סימן, זזה תא אחד ועוברת למצב הבא, לפי הכלל של המצב והסימן
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מחבר
צעדים שבוצעו
0
המכונה / אין בודק
המכונה
האפשרויות
מוצגות בסדר אקראי.
- נכונה קוראת את התא שמתחת לראש, כותבת בו סימן, זזה תא אחד ועוברת למצב הבא, לפי הכלל של המצב והסימן
- שגויה סורקת את כל הסרט ומחליטה מה לכתוב
  טעות נפוצה: Thinks a Turing machine can look at the whole tape at once, rather than the one cell under its head.
  משוב מהקטלוג
  הראש רואה תא אחד בלבד, זה שמתחתיו. כדי לדעת מה יש בהמשך הסרט, המכונה צריכה לזוז לשם, תא אחר תא, ולזכור במצב שלה מה היא מחפשת. כך המחבר “מוצא” את סוף המספר: הוא פשוט ממשיך ימינה במצב B עד שהוא קורא תא ריק.
- שגויה קופצת לכל תא שהכלל אומר
  משוב
  הראש זז תמיד תא אחד, שמאלה או ימינה. כדי להגיע רחוק הוא צריך הרבה צעדים.
- שגויה קוראת את המצב שלה מהסרט
  טעות נפוצה: Confuses the machine's state, which it keeps in itself, with the symbols written on the tape.
  משוב מהקטלוג
  המצב הוא הזיכרון הפנימי של המכונה, אות אחת בתצוגה שעל הראש; הוא לא כתוב על הסרט. הסימן הוא מה שבתא שמתחת לראש. כל כלל מחבר את שניהם: “במצב A, כשקוראים 1, כתבו…”. אותו סימן יכול להוביל לפעולות שונות במצבים שונים.
משוב לתשובה נכונה
צעד הוא תמיד אותו דבר: קוראים תא אחד, מוצאים בכרטיס את הכלל של המצב הנוכחי והסימן הזה, ואז כותבים, זזים תא אחד ומחליפים מצב. אין למכונה שום פעולה אחרת.

פתרון מלא
1. הראש קורא את הסימן בתא שמתחתיו בלבד.
2. בכרטיס הכללים מוצאים את השורה של המצב הנוכחי ואת העמודה של הסימן שנקרא.
3. הכלל אומר שלושה דברים: מה לכתוב, לאיזה כיוון לזוז תא אחד, ולאיזה מצב לעבור.
המצב נשמר בתצוגה שעל הראש, לא על הסרט.
שלב 2 מתוך 5
לפתוח את השלב
למלא את הרווח
תרגול · נבאו, ואז הסתכלו
השאלה
המחבר התחיל על 111_11 במצב A, ואחרי 3 צעדים הראש עומד על הרווח. הכלל של A כשקוראים תא ריק: כתוב 1, זוז ימינה, עבור ל־B. באיזה מצב תהיה המכונה אחרי הצעד הבא?

התשובה הנכונה
- נכונה B
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מחברקבוע
צעדים שבוצעו
3קבוע
המכונה / אין בודק
המכונה
האפשרויות
- נכונה B
- שגויה עדיין A, כי היא עדיין על המספר הראשון
  טעות נפוצה: Confuses the machine's state, which it keeps in itself, with the symbols written on the tape.
  משוב מהקטלוג
  המצב הוא הזיכרון הפנימי של המכונה, אות אחת בתצוגה שעל הראש; הוא לא כתוב על הסרט. הסימן הוא מה שבתא שמתחת לראש. כל כלל מחבר את שניהם: “במצב A, כשקוראים 1, כתבו…”. אותו סימן יכול להוביל לפעולות שונות במצבים שונים.
- שגויה עצירה: הרווח מולא, והחיבור גמור
  משוב
  הסרט עכשיו 111111, שש אחדות: אחת יותר מדי. B ו־C עוד צריכים לרוץ לסוף ולמחוק אחת.
אחרי נעילת הניבוי הסצנה משתנה
צעדים שבוצעו
4קבוע
ואז הסצנה מראה: 1 · The state as its row on the rule card: 0 for A, 1 for B, 2 for C; −1 once halted/nodes/machine/outputs/state
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
B: הכלל אומר “עבור ל־B”, והמכונה עושה בדיוק מה שהכלל אומר. הרווח מולא ב־1, והסרט הוא שישה קווים רצופים.

פתרון מלא
1. המצב A, והסימן שמתחת לראש: תא ריק.
2. הכלל של A וריק: כתוב 1, זוז ימינה, עבור ל־B.
3. אחרי הצעד: הרווח מלא, הראש על התא שאחריו, והמצב B.
המצב משתנה רק כשהכלל אומר; כאן הוא אומר.
שלב 3 מתוך 5
לפתוח את השלב
התשובה על הסרט
תרגול · נבאו, ואז הסתכלו
השאלה
המחבר מחבר 3 ו־2 שכתובים כקווי ספירה, 111_11. כמה אחדות יהיו על הסרט כשהמכונה תעצור?

התשובה הנכונה
5 ± 0.01
ניבוי מספרי נחשב נכון בטווח ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מחברקבוע
צעדים שבוצעו
0קבוע
המכונה / אין בודק
המכונה
אחרי נעילת הניבוי הסצנה משתנה
צעדים שבוצעו
60קבוע
ואז הסצנה מראה: 5 · How many 1s are on the tape now/nodes/machine/outputs/ones
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
חמש: $3 + 2 = 5$ ⁠. המכונה ממלאת את הרווח, וכך יש שש אחדות רצופות, ואז C מוחק את האחרונה.

פתרון מלא
1. בקווי ספירה מספר הוא כמות האחדות: 111 הוא $3$ ⁠, ו־11 הוא $2$ ⁠.
2. מילוי הרווח מחבר אותם לשורה אחת של $3 + 1 + 2 = 6$ ⁠ אחדות.
3. C מוחק אחת, ונשארות $6 - 1 = 5$ ⁠.
שלב 4 מתוך 5
לפתוח את השלב
לספור צעדים
תרגול · נבאו, ואז הסתכלו
השאלה
כמה צעדים יבצע המחבר עד שיעצור, כולל צעד העצירה?

התשובה הנכונה
8 ± 0.01
ניבוי מספרי נחשב נכון בטווח ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מחברקבוע
צעדים שבוצעו
0קבוע
המכונה / אין בודק
המכונה
אחרי נעילת הניבוי הסצנה משתנה
צעדים שבוצעו
60קבוע
ואז הסצנה מראה: 8 · Steps the machine has actually taken (it stops counting once halted)/nodes/machine/outputs/stepsRun
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
שמונה: שלושה צעדים על 111, אחד על הרווח, שניים על 11, אחד על התא הריק שבסוף (צעד אחורה ומעבר ל־C), ואחד שמוחק ועוצר.

פתרון מלא
1. A רץ ימינה על שלוש האחדות: $3$ ⁠ צעדים.
2. A ממלא את הרווח ועובר ל־B: $1$ ⁠ צעד.
3. B רץ על שתי האחדות: $2$ ⁠ צעדים.
4. B קורא תא ריק, זז שמאלה ועובר ל־C: $1$ ⁠ צעד.
5. C מוחק את האחדות האחרונה ועוצר: $1$ ⁠ צעד.
סך הכול $3 + 1 + 2 + 1 + 1 = 8$ ⁠.
שלב 5 מתוך 5
לפתוח את השלב
המצב השלישי
תרגול · הגיעו למטרה
השאלה
הזיזו את צעדים שבוצעו עד שהתצוגה שעל הראש מראה את המצב C, ולחצו על בדיקה.

המטרה
- 2 ± 0.01
  בתחילת השלב: 0
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מחברקבוע
צעדים שבוצעו
0
המכונה / אין בודק
המכונה
נקרא מהסצנה בנקודה
The state as its row on the rule card: 0 for A, 1 for B, 2 for C; −1 once halted/nodes/machine/outputs/state
הגדרה אחת שמגיעה למטרה
צעדים שבוצעו
7
משוב לתשובה נכונה
צעד 7: B הגיע לתא הריק שאחרי המספר, זז אחורה ועבר ל־C. המכונה נמצאת ב־C צעד אחד בלבד; בצעד 8 היא כבר עוצרת.

משוב לתשובה שגויה
עוד לא. התקדמו צעד אחר צעד ועקבו אחרי האות בתצוגה.

רמז
C מופיע רק לקראת הסוף, אחרי ש־B מגיע לתא ריק.

פתרון מלא
1. A פעיל בצעדים 0 עד 3, עד שהרווח מתמלא.
2. B פעיל מצעד 4 עד 6, עובר על 11 ומגיע לתא הריק.
3. בצעד השביעי B זז אחורה ועובר ל־C, ולכן אחרי 7 צעדים המצב הוא C.

שיעור 2 מתוך 4 · כ־25 דקות

טבלאות מצבים

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
לקרוא כרטיס
תרגול · נבאו, ואז הסתכלו
השאלה
הבונה העסוק מתחיל על סרט ריק, במצב A. הכרטיס שלו: A וריק: כתוב 1, ימינה, B. ‏B וריק: השאר ריק, ימינה, C. ‏C וריק: כתוב 1, שמאלה, C. כמה אחדות יהיו על הסרט אחרי 4 צעדים?

התשובה הנכונה
3 ± 0.01
ניבוי מספרי נחשב נכון בטווח ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
הבונה העסוקקבוע
צעדים שבוצעו
0קבוע
המכונה / אין בודק
המכונה
אחרי נעילת הניבוי הסצנה משתנה
צעדים שבוצעו
4קבוע
ואז הסצנה מראה: 3 · How many 1s are on the tape now/nodes/machine/outputs/ones
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
שלוש, 111. צעד 1 כותב 1; צעד 2 מדלג על תא; צעד 3 כותב בתא הבא וחוזר; צעד 4 ממלא את התא שדילגו עליו.

פתרון מלא
1. צעד 1: A על ריק, כותב 1 בתא 0, זז ימינה, B.
2. צעד 2: B על ריק, משאיר ריק בתא 1, זז ימינה, C.
3. צעד 3: C על ריק, כותב 1 בתא 2, זז שמאלה, נשאר C.
4. צעד 4: C על התא הריק 1, כותב 1, זז שמאלה. הסרט: 111.
שלב 2 מתוך 6
לפתוח את השלב
הבונה העסוק
תרגול · נבאו, ואז הסתכלו
השאלה
הבונה העסוק הוא מכונה של שלושה מצבים שנבחרה כי היא כותבת כמה שיותר אחדות ואז עוצרת. כמה אחדות יהיו על הסרט כשתעצור?

התשובה הנכונה
6 ± 0.01
ניבוי מספרי נחשב נכון בטווח ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
הבונה העסוקקבוע
צעדים שבוצעו
0קבוע
המכונה / אין בודק
המכונה
אחרי נעילת הניבוי הסצנה משתנה
צעדים שבוצעו
60קבוע
ואז הסצנה מראה: 6 · How many 1s are on the tape now/nodes/machine/outputs/ones
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
שש, בצעד 14. אף מכונה של שלושה מצבים ושני סימנים שעוצרת לא משאירה יותר. למכונות של חמישה מצבים, השיא הוא 4098 אחדות אחרי יותר מ־47 מיליון צעדים; לשישה מצבים, אף אחד לא יודע.

פתרון מלא
1. הריצו את הכרטיס צעד אחר צעד, או הזיזו את צעדים שבוצעו עד שהמכונה עוצרת.
2. היא עוצרת בצעד 14, כשהכלל של A וקריאת 1 שולח אותה לעצירה.
3. על הסרט: 111111, שש אחדות.
מכונות “בונה עסוק” גדלות כל כך מהר עם מספר המצבים, שאי אפשר לחשב אותן באופן כללי: זה קשור ישירות לבעיית העצירה.
שלב 3 מתוך 6
לפתוח את השלב
מונה
תרגול · בחרו
השאלה
במונה יש שלושה סימנים: ריק, 0 ו־1. הכלל שלו למצב A כשקוראים 1: כתוב 0, זוז שמאלה, הישאר ב־A. מה הכלל הזה עושה בחשבון?

התשובה הנכונה
- נכונה הוא הנשא של חיבור 1: 1 + 1 הוא 0, ו־1 עובר לספרה שמשמאל
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מונהקבוע
צעדים שבוצעו
0
המכונה / אין בודק
המכונה
האפשרויות
מוצגות בסדר אקראי.
- נכונה הוא הנשא של חיבור 1: 1 + 1 הוא 0, ו־1 עובר לספרה שמשמאל
- שגויה הוא מוחק את המספר
  משוב
  הוא כותב 0 רק כל עוד הוא עובר על אחדות. ברגע שהוא מגיע ל־0 או לתא ריק, הכלל אחר כותב שם 1.
- שגויה הוא עוצר את המכונה
  משוב
  אף כלל בכרטיס של המונה לא מוביל לעצירה; היא סופרת לנצח.
משוב לתשובה נכונה
כמו בחיבור במאונך: הוספת 1 לספרה 1 נותנת 0 ונשא שמאלה. A ממשיך שמאלה והופך כל 1 ל־0, עד שהוא מוצא 0 או תא ריק, ושם כותב 1: 011 + 1 = 100.

פתרון מלא
1. בבינארית, $1 + 1 = 10$ ⁠: ספרה 0 ונשא 1.
2. הכלל כותב 0 ומעביר את הראש שמאלה, אל הספרה הבאה, בלי להחליף מצב: הנשא ממשיך.
3. כשהנשא פוגש 0 או ריק, הכלל של A לסימנים האלה כותב 1 ועובר ל־B, שחוזר לקצה הימני.
שלב 4 מתוך 6
לפתוח את השלב
בינארית על הסרט
תרגול · חשבו
השאלה
מונה רץ כבר 30 צעדים, והסרט מראה 1000. איזה מספר זה בבסיס עשר?

התשובה הנכונה
8 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מונהקבוע
צעדים שבוצעו
30קבוע
המכונה / אין בודק
המכונה
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
The 0s and 1s written on the tape, left to right, read as a binary number (blanks skipped)/nodes/machine/outputs/number
תשובות שגויות שהשאלה מזהה
- 1000 ± 0.01
  טעות נפוצה: Reads a binary numeral as if it were decimal: takes 1000 for a thousand, or 10 for ten.
  משוב מהקטלוג
  הספרות על הסרט של המונה הן בינאריות: ערכי המקומות, מימין לשמאל, הם $1, 2, 4, 8, \ldots$ ⁠, לא $1, 10, 100, 1000$ ⁠. לכן 1000 הוא $8$ ⁠, ו־10 הוא $2$ ⁠, לא עשר. אותן ספרות, בסיס אחר.
- 4 ± 0.01
  טעות נפוצה: Reads a binary numeral as if it were decimal: takes 1000 for a thousand, or 10 for ten.
  משוב
  ארבע ספרות זה האורך, לא הערך. הספרה השמאלית שווה $8$ ⁠.
משוב לתשובה נכונה
$8$ ⁠: ב1000 דולקת רק הסיבית הרביעית מימין, שערך המקום שלה $2^3 = 8$ ⁠.

רמז
ערך המקום של הספרה הרביעית מימין הוא $2^3$ ⁠.

פתרון מלא
1. ערכי המקומות בבינארית, מימין לשמאל: $1, 2, 4, 8$ ⁠.
2. ב־1000 רק הספרה השמאלית היא 1, במקום של $8$ ⁠.
3. לכן המספר הוא $8$ ⁠.
אם עניתם $1000$ ⁠, קראתם את הספרות כאילו הן בבסיס עשר.
שלב 5 מתוך 6
לפתוח את השלב
לספור עד חמש
תרגול · הגיעו למטרה
השאלה
הזיזו את צעדים שבוצעו עד שהמונה כותב על הסרט את המספר 5, כלומר 101, ולחצו על בדיקה.

המטרה
- 5 ± 0.01
  בתחילת השלב: 0
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מונהקבוע
צעדים שבוצעו
0
המכונה / אין בודק
המכונה
נקרא מהסצנה בנקודה
The 0s and 1s written on the tape, left to right, read as a binary number (blanks skipped)/nodes/machine/outputs/number
הגדרה אחת שמגיעה למטרה
צעדים שבוצעו
15
משוב לתשובה נכונה
101 הוא $4 + 1 = 5$ ⁠. המונה מגיע אליו אחרי 16 צעדים, ובכל ספירה הוא עושה יותר צעדים, כי הנשא רץ רחוק יותר והמספר מתארך.

משוב לתשובה שגויה
עוד לא. קראו את הסרט כמספר בינארי.

רמז
המספרים שלפני 5 בבינארית: 1, 10, 11, 100.

פתרון מלא
1. 101: ערכי המקומות $4, 2, 1$ ⁠, ודולקות הספרות של $4$ ⁠ ושל $1$ ⁠: $5$ ⁠.
2. המונה מוסיף 1 בכל סבב: 1, 10, 11, 100, 101.
3. התקדמו עד שהסרט מראה 101; זה קורה בצעד 16.
שלב 6 מתוך 6
לפתוח את השלב
חזק כמו מחשב
תרגול · בחרו
השאלה
למכונת טיורינג אין אוגרים, אין ALU ואין זיכרון מלבד הסרט. מה היא יכולה לחשב, בהשוואה למעבד מהיחידה הקודמת?

התשובה הנכונה
- נכונה כל מה שהמעבד יכול לחשב, בהינתן מספיק סרט וזמן
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מונה
צעדים שבוצעו
0
המכונה / אין בודק
המכונה
האפשרויות
מוצגות בסדר אקראי.
- נכונה כל מה שהמעבד יכול לחשב, בהינתן מספיק סרט וזמן
- שגויה רק חישובים פשוטים כמו חיבור קווי ספירה
  טעות נפוצה: Thinks a Turing machine is too simple to compute what a real computer can.
  משוב מהקטלוג
  מכונת טיורינג איטית ומסורבלת, אבל היא יכולה לחשב כל מה שכל מחשב יכול, בהינתן מספיק סרט וזמן. זו טענת צ’רץ’–טיורינג, וכל ניסיון לבנות מכונה “חזקה יותר” הגיע לאותו גבול. המעבד מהיחידה הקודמת מהיר יותר, אבל לא מחשב שום דבר שהיא לא יכולה.
- שגויה יותר, כי הסרט שלה אינסופי
  משוב
  גם למעבד אפשר לחבר עוד ועוד זיכרון. כוח החישוב של שניהם זהה: אף אחד לא מחשב משהו שהשני לא יכול.
משוב לתשובה נכונה
כל מה שמחשב כלשהו יכול לחשב, מכונת טיורינג יכולה לחשב גם, לאט יותר. זה מה שהופך אותה להגדרה של “חישוב”: אם אין מכונת טיורינג שעושה משהו, אין גם מחשב שעושה אותו.

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

שיעור 3 מתוך 4 · כ־25 דקות

בעיית העצירה

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

לפתוח את השיעור

6 השלבים והתשובות שלהם

שלב 1 מתוך 6
לפתוח את השלב
עוצרת או לא
תרגול · נבאו, ואז הסתכלו
השאלה
פינג־פונג זז ימינה וחוזר, ימינה וחוזר. האם הוא יעצור אי־פעם, אם ניתן לו לרוץ 500 צעדים?

התשובה הנכונה
- נכונה לעולם לא
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
פינג־פונגקבוע
צעדים שבוצעו
20קבוע
המכונה / אין בודק
המכונה
האפשרויות
- נכונה לעולם לא
- שגויה בסוף כן, כשייגמר לו הסרט
  משוב
  לסרט של מכונת טיורינג אין סוף, ופינג־פונג גם לא צריך אותו: הוא משתמש רק בשני תאים.
- שגויה אחרי 500 צעדים
  משוב
  המכונה לא יודעת כמה צעדים ביקשנו; המונה רק עוצר את הצפייה שלנו. הכרטיס שלה לא מוביל לעצירה בשום מקום.
אחרי נעילת הניבוי הסצנה משתנה
צעדים שבוצעו
500קבוע
ואז הסצנה מראה: 0 · 1 once the machine has halted, else 0/nodes/machine/outputs/halted
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
לעולם לא. בצעד 4 המכונה חוזרת בדיוק לתמונה של צעד 2: אותו מצב, אותו תא, אותו סרט. מכאן היא חייבת לחזור על אותו מסלול שוב ושוב.

פתרון מלא
1. בצעד 1 A כותב 1 וזז ימינה ל־B; בצעד 2 B זז שמאלה חזרה ל־A.
2. מצעד 2 והלאה, כל שני צעדים המכונה חוזרת לאותה תמונה בדיוק: מצב A, ראש בתא 0, אותו סרט.
3. מכונה דטרמיניסטית שחוזרת לתמונה שכבר הייתה בה תחזור על מה שקרה אחריה, לנצח.
שלב 2 מתוך 6
לפתוח את השלב
הוכחה שהיא לא תעצור
תרגול · בחרו
השאלה
איך אפשר להיות בטוחים שפינג־פונג לעולם לא יעצור?

התשובה הנכונה
- נכונה התמונה שלו, מצב, מקום הראש והסרט, חוזרת בדיוק, ולכן הוא יחזור על אותו מסלול לנצח
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
פינג־פונג
צעדים שבוצעו
20
המכונה / אין בודק
המכונה
האפשרויות
מוצגות בסדר אקראי.
- נכונה התמונה שלו, מצב, מקום הראש והסרט, חוזרת בדיוק, ולכן הוא יחזור על אותו מסלול לנצח
- שגויה הוא רץ 500 צעדים ולא עצר
  טעות נפוצה: Concludes that a machine that has run a long time without halting must run for ever.
  משוב מהקטלוג
  ריצה ארוכה לא מוכיחה כלום. מכונה יכולה לרוץ מיליון צעדים ולעצור בצעד המיליון ואחד. הבונה העסוק של חמישה מצבים עוצר רק אחרי יותר מ־47 מיליון צעדים. על פינג־פונג אפשר להיות בטוחים מסיבה אחרת: התמונה שלו חוזרת בדיוק, ומכונה שחוזרת לתמונה שכבר הייתה בה תעבור שוב באותו מסלול לנצח.
- שגויה יש לו רק שני מצבים
  משוב
  גם מכונות של שני מצבים יכולות לעצור. המספר הקטן של מצבים לא אומר כלום לבד.
משוב לתשובה נכונה
תמונה שחוזרת היא הוכחה. ריצה ארוכה היא רק ראיה: מכונה יכולה לרוץ מיליון צעדים ולעצור בצעד הבא.

פתרון מלא
1. הצעד הבא של המכונה תלוי רק במצב, בסימן שמתחת לראש ובכרטיס.
2. אם כל התמונה חוזרת, כל מה שקרה אחריה יקרה שוב, ושוב.
3. בפינג־פונג התמונה של צעד 2 חוזרת בצעד 4, ולכן הוא מסתובב לנצח.
למונה אין חזרה כזאת, ובכל זאת הוא לא עוצר: אף כלל בכרטיס שלו לא מוביל לעצירה.
שלב 3 מתוך 6
לפתוח את השלב
מכונה שעצרה
תרגול · חשבו
השאלה
הבונה העסוק, וצעדים שבוצעו עומד על 500. המכונה עצרה כבר מזמן. כמה צעדים היא ביצעה בפועל?

התשובה הנכונה
14 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
הבונה העסוקקבוע
צעדים שבוצעו
500קבוע
המכונה / אין בודק
המכונה
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
Steps the machine has actually taken (it stops counting once halted)/nodes/machine/outputs/stepsRun
תשובות שגויות שהשאלה מזהה
- 500 ± 0.01
  טעות נפוצה: Concludes that a machine that has run a long time without halting must run for ever.
  משוב
  מכונה שעצרה לא ממשיכה לרוץ; 500 הוא רק המספר שביקשנו.
משוב לתשובה נכונה
14: מכונה שעצרה מפסיקה לספור. המונה של הסצנה יכול לבקש 500, אבל אחרי העצירה אין כלל שיופעל.

פתרון מלא
1. הבונה העסוק עוצר כשהכלל של A וקריאת 1 שולח אותו לעצירה, בצעד 14.
2. במצב העצירה אין שורה בכרטיס, ולכן אין עוד צעדים.
3. מספר הצעדים שבוצעו בפועל: 14.
אם עניתם $500$ ⁠, ספרתם את הצעדים שביקשנו ולא את אלה שהמכונה עשתה.
שלב 4 מתוך 6
לפתוח את השלב
בודק עצירה
תרגול · בחרו
השאלה
מבט פנימה על בודק עצירה: H הוא ארון סגור שמקבל כרטיס כללים ומדליק “עוצרת” או “רצה לנצח”. מה H היה צריך לעשות כדי להיות בודק עצירה אמיתי?

התשובה הנכונה
- נכונה לענות נכון על כל כרטיס, ולסיים תמיד
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מחבר
צעדים שבוצעו
0
המכונה / אין בודק
בודק עצירה
האפשרויות
מוצגות בסדר אקראי.
- נכונה לענות נכון על כל כרטיס, ולסיים תמיד
- שגויה לענות נכון על ארבעת הכרטיסים שבסצנה
  טעות נפוצה: Takes the halting problem to mean that you can never tell whether any particular program halts.
  משוב מהקטלוג
  בעיית העצירה אומרת שאין שיטה אחת שעובדת על כל תוכנית. על הרבה תוכניות מסוימות קל לענות: המחבר עוצר בצעד 8, ופינג־פונג חוזר על עצמו ולכן לעולם לא עוצר. מה שבלתי אפשרי הוא בודק שתמיד צודק, על כל כרטיס כללים שיביאו לו.
- שגויה להריץ את המכונה ולחכות לראות
  טעות נפוצה: Concludes that a machine that has run a long time without halting must run for ever.
  משוב מהקטלוג
  ריצה ארוכה לא מוכיחה כלום. מכונה יכולה לרוץ מיליון צעדים ולעצור בצעד המיליון ואחד. הבונה העסוק של חמישה מצבים עוצר רק אחרי יותר מ־47 מיליון צעדים. על פינג־פונג אפשר להיות בטוחים מסיבה אחרת: התמונה שלו חוזרת בדיוק, ומכונה שחוזרת לתמונה שכבר הייתה בה תעבור שוב באותו מסלול לנצח.
משוב לתשובה נכונה
את ארבעת הכרטיסים כאן קל לבדוק, וזה מה ש־H עושה בסצנה. השאלה של טיורינג היא על בודק כללי: מכונה אחת שעונה נכון על כל כרטיס שיביאו לה, ותמיד מסיימת.

פתרון מלא
1. בודק שרק מריץ ומחכה לא מסיים על מכונה שרצה לנצח, ולכן הוא לא עונה.
2. בודק שעובד רק על כמה כרטיסים ידועים לא עונה על השאלה הכללית.
3. בודק עצירה אמיתי: לכל כרטיס, תשובה נכונה, בזמן סופי.
שלב 5 מתוך 6
לפתוח את השלב
הטיעון של טיורינג
תרגול · בחרו
השאלה
מבט פנימה על אין בודק: D מקבלת כרטיס, שואלת את H מה יקרה כשהמכונה הזאת תקבל את הכרטיס של עצמה, ועושה ההפך: אם H אומר “עוצרת”, D רצה לנצח; אם H אומר “רצה לנצח”, D עוצרת. מה קורה כשנותנים ל־D את הכרטיס של עצמה?

התשובה הנכונה
- נכונה כל תשובה של H שגויה, ולכן H לא יכול להתקיים
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
תוכנית
מחבר
צעדים שבוצעו
0
המכונה / אין בודק
אין בודק
האפשרויות
מוצגות בסדר אקראי.
- נכונה כל תשובה של H שגויה, ולכן H לא יכול להתקיים
- שגויה D רצה לנצח, וזו כל התשובה
  משוב
  אם D רצה לנצח, זה בגלל ש־H אמר “עוצרת”, ואז H טעה. כל אחת משתי האפשרויות מסתיימת בכך ש־H טעה.
- שגויה צריך מחשב מהיר יותר כדי לדעת
  טעות נפוצה: Thinks the halting problem is a matter of speed, so a fast enough computer could decide it.
  משוב מהקטלוג
  בעיית העצירה לא קשורה למהירות. ההוכחה של טיורינג מראה שאין אלגוריתם שעונה נכון על כל תוכנית, ולא משנה כמה זמן מאפשרים לו: כל בודק שיבנו, אפשר לבנות נגדו את D, שעושה את ההפך ממה שהבודק אומר עליה. מחשב מהיר יותר רק מגיע מהר יותר לאותה סתירה.
- שגויה עוד לא יודעים; אולי מתמטיקאים יפתרו את זה
  טעות נפוצה: Thinks a universal halt checker simply has not been written yet, rather than being proved impossible.
  משוב מהקטלוג
  זה לא שעוד לא מצאו את התוכנית: הוכיחו שהיא לא יכולה להתקיים. אילו H הייתה קיימת, אפשר היה לבנות ממנה את D ולהזין לה את הכרטיס של עצמה; כל תשובה של H הייתה אז שגויה. כמו “המשפט הזה שקר”, השאלה מתהפכת על עצמה.
משוב לתשובה נכונה
אם H אומר ש־D עוצרת, D רצה לנצח; אם H אומר שהיא רצה לנצח, היא עוצרת. בשני המקרים H טועה, ולכן בודק שתמיד צודק לא יכול להתקיים. זו בעיית העצירה: טיורינג, 1936.

פתרון מלא
1. נניח ש־H קיים ותמיד צודק.
2. אם H עונה “D עוצרת”, D עושה את ההפך ורצה לנצח: H טעה.
3. אם H עונה “D רצה לנצח”, D עוצרת: H טעה שוב.
4. כל תשובה סותרת את ההנחה, ולכן ההנחה שגויה: אין H כזה.
זו הוכחה, לא קושי טכני: שום מהירות ושום זמן לא יעזרו.
שלב 6 מתוך 6
לפתוח את השלב
מה זה אומר
תרגול · בחרו
השאלה
מה בעיית העצירה לא אומרת?

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

פתרון מלא
1. ההוכחה בונה, לכל בודק מוצע, מכונה אחת שהוא טועה עליה: D.
2. היא לא אומרת כלום נגד בדיקה של המחבר, של פינג־פונג או של כל תוכנית מסוימת אחרת.
3. לכן הטענה “אי אפשר לדעת על שום תוכנית” שגויה; הנכונה היא “אין בודק שתמיד צודק”.

שיעור 4 מתוך 4 · כ־25 דקות

כללים פשוטים, התנהגות מורכבת

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

לפתוח את השיעור

8 השלבים והתשובות שלהם

שלב 1 מתוך 8
לפתוח את השלב
הכללים
תרגול · בחרו
השאלה
בכללים של משחק החיים, נולד עם 3 ושורד עם 2 או 3. תא חי עם ארבעה שכנים חיים: מה יקרה לו בדור הבא?

התשובה הנכונה
- נכונה הוא מת
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)
שורד עם
2 או 3 (החיים)
התחלה
R־פנטומינו
תאים / צורות
שכנים
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 0
האפשרויות
מוצגות בסדר אקראי.
- נכונה הוא מת
- שגויה הוא שורד, כי יש לו יותר משניים
  משוב
  שורד רק עם בדיוק 2 או 3. עם ארבעה או יותר הוא מת, “מצפיפות”.
- שגויה הוא מוליד תא חדש לידו
  משוב
  תא נולד רק בתא מת שיש לו בדיוק שלושה שכנים חיים. תאים חיים לא מולידים; הלידה תלויה רק בספירה של התא הריק.
משוב לתשובה נכונה
ארבעה שכנים הם יותר מדי: רק 2 או 3 שומרים תא חי. עם 0 או 1 הוא מת “מבדידות”, ועם 4 ומעלה “מצפיפות”.

פתרון מלא
1. התא חי, ולכן חל עליו כלל ההישרדות, לא כלל הלידה.
2. הוא שורד רק אם מספר השכנים החיים שלו הוא 2 או 3.
3. יש לו 4, ולכן בדור הבא הוא מת.
שלב 2 מתוך 8
לפתוח את השלב
דור אחד
תרגול · נבאו, ואז הסתכלו
השאלה
התחלה היא R־פנטומינו: חמישה תאים חיים, ומבט פנימה על שכנים מראה כמה שכנים חיים יש לכל תא. כמה תאים חיים יהיו בדור 1?

התשובה הנכונה
6 ± 0.01
ניבוי מספרי נחשב נכון בטווח ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)קבוע
שורד עם
2 או 3 (החיים)קבוע
התחלה
R־פנטומינוקבוע
תאים / צורות
שכניםקבוע
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 0
אחרי נעילת הניבוי הסצנה משתנה
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 1
ואז הסצנה מראה: 6 · Live cells in view at firstGeneration/nodes/board/outputs/population
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
שישה: תא חי אחד מת, זה שבאמצע, עם ארבעה שכנים, ושני תאים ריקים נולדים, כל אחד עם שלושה. $5 - 1 + 2 = 6$ ⁠.

פתרון מלא
1. לכל אחד מחמשת התאים החיים סופרים שכנים: לתא האמצעי 4, ולשאר 2 או 3. האמצעי מת; ארבעה שורדים.
2. לתאים הריקים סביב: לשניים מהם, בצד שמאל, יש בדיוק 3 שכנים חיים, והם נולדים.
3. בדור 1: $4 + 2 = 6$ ⁠ תאים חיים.
כל התאים מתעדכנים בבת אחת, לפי הספירה של הדור הנוכחי.
שלב 3 מתוך 8
לפתוח את השלב
לספור לידות
תרגול · חשבו
השאלה
באותו R־פנטומינו, בדור 0: בכמה תאים ריקים ייוולדו תאים חדשים בדרך לדור 1?

התשובה הנכונה
2 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)קבוע
שורד עם
2 או 3 (החיים)קבוע
התחלה
R־פנטומינוקבוע
תאים / צורות
שכניםקבוע
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 0
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
Dead cells in view that are born in the next generation/nodes/board/outputs/births
תשובות שגויות שהשאלה מזהה
- 0 ± 0.01
  טעות נפוצה: Counts only the four neighbours above, below and to the sides of a cell, leaving out the four diagonals.
  משוב מהקטלוג
  במשחק החיים לכל תא יש שמונה שכנים: ארבעה בצדדים וארבעה באלכסונים, כמו המשבצות שמסביב למלך בשחמט. ב־R־פנטומינו, התא הריק בפינה השמאלית העליונה נוגע בשלושה תאים חיים רק כשסופרים גם את האלכסון, ולכן הוא נולד.
משוב לתשובה נכונה
שניים: התא הריק משמאל לשורה העליונה והתא הריק משמאל לשורה התחתונה. לכל אחד מהם בדיוק שלושה שכנים חיים, כשסופרים גם באלכסון.

רמז
בשלב שכנים המספרים שבתאים הריקים הם הספירה שלהם.

פתרון מלא
1. הצורה, מלמעלה למטה: .OO, OO., .O..
2. לתא הריק בפינה השמאלית העליונה שכנים חיים: מימינו, מתחתיו ובאלכסון מתחתיו מימין, שלושה. הוא נולד.
3. לתא הריק בפינה השמאלית התחתונה: מעליו, מימינו ובאלכסון מעליו מימין, שלושה. גם הוא נולד.
4. לכל שאר התאים הריקים יש פחות או יותר משלושה.
אם עניתם $0$ ⁠, ספרתם רק ארבעה שכנים לכל תא; גם האלכסונים נחשבים.
שלב 4 מתוך 8
לפתוח את השלב
צורות שזזות
תרגול · נבאו, ואז הסתכלו
השאלה
התחלה היא גן חיות של צורות: גוש, מהבהבים, פולסר, ובצד ימין למטה רחפן, חמישה תאים בצורת חץ. מה יעשה הרחפן?

התשובה הנכונה
- נכונה ינוע באלכסון על פני הלוח, ויחזור לאותה צורה כל ארבעה דורות
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)קבוע
שורד עם
2 או 3 (החיים)קבוע
התחלה
גן חיות של צורותקבוע
תאים / צורות
תאים
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 0
האפשרויות
- נכונה ינוע באלכסון על פני הלוח, ויחזור לאותה צורה כל ארבעה דורות
- שגויה יישאר במקום, כמו הגוש
  משוב
  הגוש דומם כי לכל תא בו יש בדיוק שלושה שכנים ואף תא ריק סביבו לא נולד. ברחפן תאים מתים ונולדים בכל דור.
- שגויה ימות, כי לחלק מהתאים שלו יש רק שכן אחד
  משוב
  תא אחד מת, אבל בכל דור נולדים תאים חדשים לידו. הצורה כולה שורדת וזזה.
אחרי נעילת הניבוי הסצנה משתנה
תאים / צורות
צורות
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 40
ואז הסצנה מראה: 2 · Groups that move across the board, the gun's gliders included (needs firstGeneration ≥ 30)/nodes/board/outputs/spaceships
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
הוא נע: אחרי ארבעה דורות הצורה חוזרת, אבל תא אחד באלכסון. אף תא לא זז; תאים מתים בצד אחד ונולדים בצד השני, והצורה זוחלת. בשלב צורות הרחפן צבוע כחללית.

פתרון מלא
1. בכל דור תאים מתים בצד האחורי של הרחפן ותאים נולדים בצד הקדמי.
2. אחרי ארבעה דורות הצורה זהה לצורה ההתחלתית, מוזזת תא אחד ימינה ותא אחד קדימה.
3. לכן הוא ממשיך באלכסון, ארבעה דורות לכל צעד, עד שהוא פוגש משהו.
שלב 5 מתוך 8
לפתוח את השלב
דומם או מהבהב
תרגול · חשבו
השאלה
מבט פנימה על צורות, בדור 40 של גן החיות: כל קבוצה צבועה לפי מה שהיא עושה. כמה מהקבוצות הן צורות דוממות, כאלה שלא משתנות בכלל?

התשובה הנכונה
4 ± 0.01
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)קבוע
שורד עם
2 או 3 (החיים)קבוע
התחלה
גן חיות של צורותקבוע
תאים / צורות
צורותקבוע
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 40
מתקבלת בטווח
± 0.01
מחושבת מהסצנה בהגדרה של השלב
Groups of cells that stay exactly the same (needs firstGeneration ≥ 30, else 0)/nodes/board/outputs/stillLifes
תשובות שגויות שהשאלה מזהה
- 9 ± 0.01
  טעות נפוצה: Counts an oscillator, which keeps changing and comes back, as a still life.
  משוב מהקטלוג
  צורה דוממת לא משתנה בכלל, מדור לדור: גוש, כוורת, כיכר לחם, סירה. מתנד משתנה בכל דור וחוזר לצורה הראשונה אחרי כמה דורות, כמו המהבהב, שעובר בין קו עומד לקו שוכב. בשלב צורות הם צבועים בצבעים שונים.
משוב לתשובה נכונה
ארבע: הגוש, הכוורת, כיכר הלחם והסירה, בשורה האחורית. המהבהב, הקרפדה, המגדלור, הפולסר והפנטדקתלון הם מתנדים: הם משתנים וחוזרים.

רמז
השוו את הצבעים למקרא: דומם, מתנד, חללית.

פתרון מלא
1. צורה דוממת: כל תא חי בה שורד (2 או 3 שכנים), ושום תא ריק סביבה לא נולד.
2. בשורה האחורית יש ארבע כאלה: גוש, כוורת, כיכר לחם, סירה.
3. המתנדים חוזרים לצורתם רק אחרי כמה דורות, ולכן הם לא דוממים.
אם עניתם $9$ ⁠, ספרתם גם את חמשת המתנדים.
שלב 6 מתוך 8
לפתוח את השלב
לשנות את הכלל
תרגול · נבאו, ואז הסתכלו
השאלה
שורד עם יתחלף לאף פעם: כל תא חי מת בדור הבא, אלא אם נולד מחדש. מה יקרה למרק האקראי?

התשובה הנכונה
- נכונה הכול ימות, והלוח יתרוקן
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)קבוע
שורד עם
2 או 3 (החיים)קבוע
התחלה
מרק אקראיקבוע
תאים / צורות
תאים
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 30
האפשרויות
- נכונה הכול ימות, והלוח יתרוקן
- שגויה הלוח ירתח, כי תאים נולדים כל הזמן
  משוב
  לידות עם 3 בלבד, בלי שום הישרדות, לא מחזיקות מעמד: קבוצות שנולדו מתות מיד, ונשארות פחות ופחות לידות.
- שגויה בערך אותו דבר כמו במשחק החיים
  טעות נפוצה: Assumes complex behaviour can only come from complex rules.
  משוב מהקטלוג
  הכללים של משחק החיים נכנסים במשפט אחד, ועדיין מהם יוצאים רחפנים, תותחים שיורים רחפנים, ואפילו מחשב שלם שבנו מתאים: הוכח שמשחק החיים יכול לחשב כל מה שמכונת טיורינג יכולה. גם מכונת טיורינג עצמה היא כמה כללים פשוטים. המורכבות באה מחזרה עצומה על כלל פשוט, לא מהכלל.
אחרי נעילת הניבוי הסצנה משתנה
שורד עם
אף פעםקבוע
ואז הסצנה מראה: 1 · How the rule treats a random soup: 1 dies out, 2 freezes into a few still shapes, 3 grows into a frozen crust, 4 boils for ever, 5 shapes last, move and collide/nodes/board/outputs/regime
ניבוי אף פעם לא נחשב כישלון: בכל מקרה הלומדים רואים את התוצאה ואת ההסבר.
משוב לתשובה נכונה
הלוח מתרוקן. שינוי אחד קטן בכלל, ומהעולם העשיר של משחק החיים לא נשאר כלום. בהגדרת שורד עם אחרת הלוח ירתח או יקפא: ההתנהגות רגישה מאוד לכלל.

פתרון מלא
1. בלי הישרדות, כל תא חי מת אחרי דור אחד.
2. תא נולד רק בתא ריק עם בדיוק שלושה שכנים חיים, וכל דור יש פחות תאים חיים שיכולים להוליד.
3. תוך כמה דורות לא נשאר אף תא.
שלב 7 מתוך 8
לפתוח את השלב
כלל שקופא
תרגול · הגיעו למטרה
השאלה
מצאו כלל, בעזרת נולד עם ושורד עם, שבו המרק האקראי קופא תוך פחות ממאה דורות לכמה צורות דוממות ומהבהבים, ולחצו על בדיקה.

המטרה
- 2 ± 0.01
  בתחילת השלב: 5
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)
שורד עם
2 או 3 (החיים)
התחלה
מרק אקראיקבוע
תאים / צורות
תאים
הגדרות נוספות
First generation/nodes/board/props/firstGeneration = 30
נקרא מהסצנה בנקודה
How the rule treats a random soup: 1 dies out, 2 freezes into a few still shapes, 3 grows into a frozen crust, 4 boils for ever, 5 shapes last, move and collide/nodes/board/outputs/regime
הגדרה אחת שמגיעה למטרה
נולד עם
4
שורד עם
2 או 3 (החיים)
משוב לתשובה נכונה
נולד עם 4, שורד עם 2 או 3: לידה קשה מדי, ולכן הצורות לא מצליחות לגדול ולנוע, והלוח נרגע מהר. רק צירוף אחד מתוך שישה־עשר נותן את זה.

משוב לתשובה שגויה
עוד לא. כלל שקופא צריך לידות קשות יותר.

רמז
השאירו את שורד עם כמו במשחק החיים, ושנו את נולד עם.

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

התשובה הנכונה
- נכונה מחשב שלם: משחק החיים יכול לחשב כל מה שמכונת טיורינג יכולה
הגדרות, אפשרויות ומשוב
הסצנה בשלב הזה
נולד עם
3 (החיים)
שורד עם
2 או 3 (החיים)
התחלה
תותח רחפנים
תאים / צורות
צורות
האפשרויות
מוצגות בסדר אקראי.
- נכונה מחשב שלם: משחק החיים יכול לחשב כל מה שמכונת טיורינג יכולה
- שגויה רק צורות פשוטות, כי הכלל פשוט
  טעות נפוצה: Assumes complex behaviour can only come from complex rules.
  משוב מהקטלוג
  הכללים של משחק החיים נכנסים במשפט אחד, ועדיין מהם יוצאים רחפנים, תותחים שיורים רחפנים, ואפילו מחשב שלם שבנו מתאים: הוכח שמשחק החיים יכול לחשב כל מה שמכונת טיורינג יכולה. גם מכונת טיורינג עצמה היא כמה כללים פשוטים. המורכבות באה מחזרה עצומה על כלל פשוט, לא מהכלל.
- שגויה רק רעש אקראי
  משוב
  משחק החיים דטרמיניסטי לגמרי: אותה התחלה נותנת תמיד אותו לוח. ממנו בנו רחפנים, תותחים ושערים לוגיים.
משוב לתשובה נכונה
רחפנים יכולים לשאת סיביות, ותותח רחפנים הוא שעון. מאלה בנו שערים לוגיים, זיכרון, ואפילו מכונת טיורינג שלמה מתאים. לכן גם על משחק החיים חלה בעיית העצירה: אין שיטה שתגיד תמיד אם צורה תיעלם בסוף.

פתרון מלא
1. תותח רחפנים יורה רחפן כל שלושים דורות: זרם של סיביות.
2. התנגשויות בין רחפנים יכולות לבטל או להעביר אותם: אלה שערים לוגיים.
3. משערים וזיכרון בונים מחשב, ולכן משחק החיים שלם טיורינג.
המורכבות לא נמצאת בכלל; היא נוצרת מחזרה עליו מיליוני פעמים.

בכל היחידה · 11 טעויות נפוצות

קטלוג הטעויות הנפוצות

כל טעות נפוצה שהיחידה מזהה, בכמה מילים. פתחו טעות כדי לראות מה הלומדים קוראים כשהתשובה מתאימה לה, ואיפה היא נשאלת.

תוכן העניינים

מכונת טיורינג

קורא, כותב, זז

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

פתרון מלא

למלא את הרווח

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא

התשובה על הסרט

השאלה

התשובה הנכונה

הסצנה בשלב הזה

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא

לספור צעדים

השאלה

התשובה הנכונה

הסצנה בשלב הזה

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא

המצב השלישי

השאלה

המטרה

הסצנה בשלב הזה

הגדרה אחת שמגיעה למטרה

רמז

פתרון מלא

טבלאות מצבים

לקרוא כרטיס

השאלה

התשובה הנכונה

הסצנה בשלב הזה

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא

הבונה העסוק

השאלה

התשובה הנכונה

הסצנה בשלב הזה

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא

מונה

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

פתרון מלא

בינארית על הסרט

השאלה

התשובה הנכונה

הסצנה בשלב הזה

תשובות שגויות שהשאלה מזהה

רמז

פתרון מלא

לספור עד חמש

השאלה

המטרה

הסצנה בשלב הזה

הגדרה אחת שמגיעה למטרה

רמז

פתרון מלא

חזק כמו מחשב

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

פתרון מלא

בעיית העצירה

עוצרת או לא

השאלה

התשובה הנכונה

הסצנה בשלב הזה

האפשרויות

אחרי נעילת הניבוי הסצנה משתנה

פתרון מלא