איך לבנות מחשב אוריגמי | מגזין קוונטה

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

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

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

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

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

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

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

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

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

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

זה ידוע מאז סוף שנות התשעים שפשוט יותר אנלוגי חד מימדי של משחק החיים של קונווי הושלם טיורינג. האל וזכרביץ' הבינו איך לכתוב את הגרסה הזו של החיים במונחים של פעולות לוגיות. "בסופו של דבר היינו צריכים להשתמש רק בארבעה שערים: AND, OR, NAND ו- NOR", אמר זכרביץ', בהתייחס לשני שערים פשוטים נוספים. אבל כדי לשלב את השערים השונים הללו, הם היו צריכים לבנות גאדג'טים חדשים שקלטו אותות זרים ואפשרו לאותות אחרים להסתובב ולהצטלב מבלי להפריע זה לזה. "זה היה החלק הכי קשה", אמר זכרביץ', "להבין איך לגרום להכל להסתדר כמו שצריך". אחרי שהיא והאל הצליחו להתאים את הגאדג'טים שלהם זה לזה, הם יכלו לקודד את כל מה שהם צריכים בקפלי נייר, ובכך להראות שהאוריגמי הושלם עם טיורינג.

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

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

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

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