מהי תוכנה? מהו אלגוריתם? ולמי יש בבית מכונת טיורינג?

מהי תוכנה? איך היא עובדת? ומה הקשר בין פקודות בשפת תכנות לשפה בינארית עם אחדות ואפסים? אנסה לענות.

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

זה הרעיון העומד מאחורי המחשב. מכונה רב שימושית.

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

אתם כותבים מספר למכונה, היא מוציאה שורש ריבועי. כתבתם 9, המכונה כתבה לכם 3. כתבתם 1024, המכונה החזירה לכם 32. כתבתם 1 המכונה החזירה 1.

בואו לא ניכנס לעניין המספרים השלמים ואיך היא תוציא מספר אי-רציונלי כפלט ל-2… 🙂

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

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

אבל החבר שלכם הפתיע אתכם במכונה נחמדה אחרת שיודעת לחשב סינוס. גאוני! כתבתם שם פַּי (או 180 מעלות), המכונה כתבה לכם 0. כתבתם 24.5 פי, המכונה כתבה 1.

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

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

אלן טיורינג נחלץ לעזרתך

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

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

מגניב.

אז מהו אלגוריתם? איך הוא קשור?

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

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

דוגמא לאלגוריתם: הכנת קפה.

"לך למטבח, שים מים בקומקום, תלחץ על כפתור ההדלקה, שים שני כפיות סוכר בכוס וכפית אחת של קפה, תמלא את הכוס ב-2/3 מים רתוחים ותוסיף מעט חלב"

אחלה, נכון?

לא.

ישאל אתכם הרובוט: מהו קומקום?

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

מהם הוראות בסיסיות?

בשביל נהג שנשלח להביא פיצה מהפיצריה, הוראות בסיסיות לאלגוריתם הבאת הפיצה הן: "סע לרח' ארלוזורוב, תחנה כחוק, תקנה פיצה בפיצריה וחזור הביתה"

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

הקשר למחשב האישי

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

פקודות המחשב הבסיסיות, מעצם היותו מחשב בינארי, הן מספרים בינאריים כמו 10001101 ו- 11100100. הוראה אחת יכולה להיות שורש, הוראה אחרת היא סינוס (ונעזוב לרגע את העובדה ששורש וסינוס הן לא הוראות יסודיות במחשב אמיתי), כאשר גם חיבור, חיסור, כפל וחילוק לא נפקדים. הוראות נוספות הן "קפוץ להוראה ה-n הבאה", כאשר ה-n הוא הנתון שבא עם ההוראה, או כמו בדוגמאות שלי: (קפוץ, 8), יקפוץ 8 הוראות קדימה, ואילו (קפוץ, -1) יקפוץ הוראה אחת אחורנית.

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

אז למי יש בבית מכונת טיורינג אוניברסלית?

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

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

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

מכונת החישוב המשוכללת בכל העניין הזה, היא בסה"כ המעבד (CPU), המבצע פעולות חישוב על פקודות שיושבות בזיכרון. כל המארז הגדול של המחשב, כולל דיסק-קשיח, כונן אופטי (CD / DVD) וכו' הם התקנים פריפריאליים לעניינינו, הם לא מבצעים את עיקר החישוב. למרות שגם להם יש בקרים עצמאיים, הם פועלים רק ע"פ ההוראות שהמעבד מבצע ומעביר אל ההתקנים (בהמשך לדוגמאות שלי, למעבד יש גם את הפקודה (שמור, 11001001), (צרוב, 11110011) וכו').

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

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

ישנם הרבה דרכים לראות את אותם הנתונים, מכיוון שהנתונים שנמצאים שם בפנים הם רק ערכים של 1 ו-0, דהיינו רשימה ארוכה מאוד (מאוד מאוד) של ספרות כאלו (הנקראות "סיביות", או "ביטים" באנגלית, קיצור של "ספרה בינארית"). גם האותיות שאתם קוראים עכשיו הם בעצם מניפולציה על אותן הספרות. אם נחשוב על האות א כעל 00001 ועל האות ב כעל 00010 , על האות ג כעל 00011, ונוסיף עוד כמה סימני פיסוק לתוך העסק הזה כמו למשל ש-11101 יהיה נקודה, 11110 יהיה פסיק ו-11111 יהיה רווח, אז אם יש לנו חבר רחוק שיש לו תרגומון לשפה הזו, נוכל לשלוח לו מכתב שבו מופיעות רק הספרות 0 ו-1 והוא יוכל לפענח אותו ולקרוא את כל המכתב בעברית יפה. זה נקרא קידוד, וזו הסיבה למה לפעמים עברית נראית כג'יבריש – אם לחבר שלנו יהיה תרגומון לא נכון והוא יבין את 00001 כ-A, את 00010 כ-B וכו', הוא יפענח את המכתב שלנו כמשהו באותיות אנגליות אבל מעוות מאוד. משפטים באנגלית הוא כנראה לא יקבל מזה.

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

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

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

בעז.