מה הקשר בין מוכר סבון בפינית, מחשבים ופלינדרומים?

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

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

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

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

 

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

פלינדרום כמבחן פשוט למכונת טיורינג

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

 

כך זה ייראה בתיאוריה:

* המכונה תתחיל בתא הראשון, תסמן אותו (למשל באות X), ותזכור את התו שנמצא בו.

* לאחר מכן תנוע לצד השני, עד שתגיע לתו האחרון, ותשווה אותו לזה שסומן.

* אם הם תואמים, היא תסמן גם את התו הזה.

* עכשיו היא חוזרת פנימה – משווה בין התו השני מההתחלה לשני מהסוף, וכך הלאה.

 

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

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

למה זה חשוב?

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

 

מכונת טיורינג מוכיחה שכל חישוב, מורכב ככל שיהיה, ניתן לפרק לסדרה של הוראות פשוטות. בדיוק כמו שהמילה "saippuakivikauppias" נראית מסובכת אך מתגלה כברת-דרך הגיונית כשמפרקים אותה שלב אחר שלב.

לסיום

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

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

ואולי זה הסוד של גאונות אמיתית: לקחת משהו שנראה בלתי אפשרי, ולהפוך אותו לפשוט ומובן.