לחלק א' >>>
בשביל להבין את המאמר צריך קודם להבין את ההקשר התיאורטי שהמאמר חי בו. למחשבים שאנחנו מכירים ואוהבים ואוהבים לשנוא יש הרבה תיאורים מתמטיים. כל התיאורים האלו שקולים אחד לשני, במובן שהם כולם מתארים מכונה שיכולה לחשב בדיוק את אותם הדברים באותה המהירות, אבל לעבודה עם כל תיאור כזה יתרונות וחסרונות. כותבי המאמר בחרו להשתמש בתיאור ספציפי של מערכות חישוב הנקרא מעגל בוליאני [1]. היתרון בתיאור הזה הוא שקל להוכיח עליו דברים, החיסרון הוא שזו דרך די מסורבלת להציג אלגוריתמים בפועל. כבר סיפרנו לכם על מעגלים בוליאניים בפוסט קודם על מחשוב קוונטי [2], אבל עכשיו ניתן תיאור קצת יותר מעמיק.
בגדול, שער בוליאני (או שער לוגי) [3] הוא קופסה שמקבלת מספר, או כמה מספרים, ומוציאה מספר. נהוג לדמיין שער לוגי כקופסה פיזית שיש לה "רגליים" שהם בעצם כבלי חשמל שנכנסים ויוצאים ממנה. על כל רגל נכנסת אנחנו יכולים "לשלוח" את המספר 0 או את המספר 1, ולפי המספרים האלה הקופסה תשלח אפסים או אחדים על רגלי היציאה. לדוגמה, אפשר לבנות קופסה שיש לה 8 רגלי כניסה ורגל יציאה אחת. על ארבע רגלי הכניסה הראשונות נשלח מספר כלשהו (מקודד בבינארית, כלומר מספר בין 0 ל15), ועל ארבע האחרונות נשלח מספר אחר. הקופסה תוציא לנו 0 אם המספר הראשון יותר גדול ו-1 אם לא. זו בעצם קופסה שיודעת להשוות בין שני מספרים.
אפשר לחבר קופסאות כאלה זו לזו בכל מני צורות. איך? ניקח את רגל היציאה של קופסה אחת ונחבר אותה לרגל הכניסה של קופסה אחרת. עכשיו, חלק ממה שיכנס לקופסה השניה הוא חלק ממה שיצא מהקופסה הראשונה. כשלוקחים הרבה קופסאות כאלו ומחברים אותן אחת לשניה בצורה כזו מקבלים דבר הנקרא "מעגל בוליאני". למעשה, יש שער ממש פשוט שנקרא NAND. יש לו שתי רגלי כניסה ורגל יציאה אחת, והוא מוציא 0 אם ורק אם הכניסו לו אחד בשתי הרגליים. ידוע שבעזרת מעגלים שמורכבים מהשער הזה בלבד אפשר לבצע כל חישוב שהמחשב הביתי שלך יודע לבצע [4].

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

מעגל בוליאני בעומק 3 עם 16 רגלי כניסה ורגל יציאה אחת

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

קרדיט תמונה ראשית: Stefan506 via Wikimedia