วิธีสร้างคอมพิวเตอร์ Origami | นิตยสารควอนต้า

ในปี 1936 อลัน ทัวริง นักคณิตศาสตร์ชาวอังกฤษ เกิดแนวคิดเกี่ยวกับคอมพิวเตอร์อเนกประสงค์ มันเป็นอุปกรณ์ง่ายๆ: แถบเทปจำนวนนับไม่ถ้วนที่ปกคลุมไปด้วยศูนย์และหนึ่ง พร้อมด้วยเครื่องจักรที่สามารถเลื่อนไปมาตามแนวเทป โดยเปลี่ยนศูนย์เป็นหนึ่งและในทางกลับกันตามกฎบางชุด เขาแสดงให้เห็นว่าอุปกรณ์ดังกล่าวสามารถใช้ในการคำนวณได้

ทัวริงไม่ได้ตั้งใจให้แนวคิดของเขานำไปปฏิบัติในการแก้ปัญหาได้ แต่เป็นการนำเสนอวิธีการอันล้ำค่าในการสำรวจธรรมชาติของการคำนวณและขีดจำกัดของมัน ตลอดหลายทศวรรษนับตั้งแต่แนวคิดสำคัญดังกล่าว นักคณิตศาสตร์ได้รวบรวมรายชื่อแผนงานคอมพิวเตอร์ที่ใช้งานได้จริงน้อยกว่านั้นด้วยซ้ำ โดยหลักการแล้วเกมอย่าง Minesweeper หรือ Magic: The Gathering สามารถใช้เป็นคอมพิวเตอร์เอนกประสงค์ได้ สิ่งที่เรียกว่าออโตมาตะแบบเซลลูลาร์ได้เหมือนกับของจอห์น คอนเวย์ เกมชีวิตซึ่งเป็นชุดกฎสำหรับการพัฒนาสี่เหลี่ยมจัตุรัสขาวดำบนตารางสองมิติ

ในเดือนกันยายน 2023, อินนา ซาคาเรวิช ของมหาวิทยาลัยคอร์เนล และ โทมัส ฮัลล์ ของ Franklin & Marshall College แสดงให้เห็นว่าสิ่งใดก็ตามที่สามารถคำนวณได้ สามารถคำนวณโดยการพับกระดาษ. พวกเขาพิสูจน์ว่า origami คือ "ทัวริงสมบูรณ์" ซึ่งหมายความว่า เช่นเดียวกับเครื่องจักรทัวริง มันสามารถแก้ปัญหาการคำนวณที่เข้าใจยากโดยให้เวลาเพียงพอ

Zakharevich ผู้ชื่นชอบการพับกระดาษโอริกามิมาตลอดชีวิต เริ่มคิดถึงปัญหานี้ในปี 2021 หลังจากสะดุดกับวิดีโอที่อธิบายความสมบูรณ์ของทัวริงของเกมแห่งชีวิต “ ฉันชอบ origami ซับซ้อนกว่า Game of Life มาก” Zakharevich กล่าว “หากเกมแห่งชีวิตทัวริงเสร็จสมบูรณ์แล้ว origami ก็ควรจะเสร็จสมบูรณ์เช่นกัน”

แต่นี่ไม่ใช่ความเชี่ยวชาญของเธอ แม้ว่าเธอจะพับกระดาษโอริกามิมาตั้งแต่เด็ก “ถ้าคุณต้องการมอบสิ่งที่ซับซ้อนอย่างยิ่งซึ่งต้องใช้กระดาษขนาด 24 นิ้วและมี 400 ขั้นให้ฉัน ฉันก็ทำเสร็จแล้ว” เธอกล่าว การวิจัยทางคณิตศาสตร์เกี่ยวข้องกับขอบเขตเชิงนามธรรมของโทโพโลยีพีชคณิตและทฤษฎีหมวดหมู่มากกว่ามาก เธอจึงส่งอีเมลไปหาฮัลล์ ผู้ซึ่งศึกษาคณิตศาสตร์โอริกามิเต็มเวลา

“เธอส่งอีเมลหาฉันโดยไม่ได้ตั้งใจ และฉันก็แบบว่า ทำไมนักทอพอโลยีเชิงพีชคณิตถึงถามฉันเกี่ยวกับเรื่องนี้” ฮัลล์กล่าวว่า แต่เขาตระหนักว่าเขาไม่เคยคิดเลยจริงๆ ว่า origami จะเป็นทัวริงที่สมบูรณ์หรือไม่ “ฉันก็ประมาณว่าน่าจะใช่ แต่จริงๆ แล้วฉันไม่รู้”

ดังนั้นเขาและซาคาเรวิชจึงออกเดินทางเพื่อพิสูจน์ว่าคุณสามารถสร้างคอมพิวเตอร์จากการพับกระดาษได้ ขั้นแรก พวกเขาต้องเข้ารหัสอินพุตและเอาท์พุตเชิงคำนวณ เช่นเดียวกับการดำเนินการเชิงตรรกะขั้นพื้นฐาน เช่น AND และ OR เหมือนกับพับกระดาษ หากพวกเขาสามารถแสดงให้เห็นว่าโครงการของพวกเขาสามารถจำลองแบบจำลองการคำนวณอื่น ๆ ที่ทราบว่าทัวริงเสร็จสมบูรณ์แล้ว พวกเขาจะบรรลุเป้าหมาย

การดำเนินการทางลอจิคัลรับอินพุตหนึ่งรายการขึ้นไป (แต่ละอินพุตเขียนเป็น TRUE หรือ FALSE) และแยกเอาต์พุต (TRUE หรือ FALSE) ตามกฎที่กำหนด ในการทำงานโดยใช้กระดาษ นักคณิตศาสตร์ได้ออกแบบแผนภาพเส้นที่เรียกว่ารูปแบบรอยพับ ซึ่งระบุตำแหน่งที่จะพับกระดาษ การจีบในกระดาษแสดงถึงการป้อนข้อมูล หากคุณพับไปตามเส้นเดียวในรูปแบบรอยพับ รอยพับจะพลิกไปด้านหนึ่ง ซึ่งระบุค่าอินพุตเป็น TRUE แต่ถ้าคุณพับกระดาษตามเส้นอื่น (ใกล้เคียง) รอยจีบจะพลิกไปด้านตรงข้าม แสดงว่าเป็น FALSE

จีบอินพุตสองอันนี้จะป้อนเข้าไปในรอยพับที่ซับซ้อนที่เรียกว่าอุปกรณ์ แกดเจ็ตเข้ารหัสการดำเนินการเชิงตรรกะ เพื่อที่จะพับทั้งหมดนี้และยังคงพับกระดาษให้เรียบ ซึ่งเป็นข้อกำหนดที่ฮัลล์และซาคาเรวิชกำหนด พวกเขาจึงรวมจีบครั้งที่สามที่ถูกบังคับให้พับในลักษณะเฉพาะ ถ้าจีบพลิกด้านเดียว แสดงว่าเอาท์พุตเป็น TRUE หากพลิกกลับด้านผลลัพธ์จะเป็น FALSE

นักคณิตศาสตร์ได้ออกแบบอุปกรณ์ต่างๆ ที่เปลี่ยนอินพุตให้เป็นเอาต์พุตตามการดำเนินการเชิงตรรกะต่างๆ “มันเป็นการเล่นกับกระดาษและส่งรูปภาพให้กันและกัน … จากนั้นจึงเขียนข้อพิสูจน์ที่เข้มงวดว่าสิ่งเหล่านี้ทำงานตามที่เราบอก” ฮัลล์กล่าว

เป็นที่ทราบกันมาตั้งแต่ปลายทศวรรษ 1990 ว่าง่ายกว่า อะนาล็อกมิติเดียว ของเกมแห่งชีวิตของคอนเวย์กำลังทัวริงเสร็จสมบูรณ์ ฮัลล์และซาคาเรวิชคิดวิธีเขียน Life เวอร์ชันนี้ในแง่ของการดำเนินการเชิงตรรกะ “เราจำเป็นต้องใช้เพียงสี่ประตูเท่านั้น: AND, OR, NAND และ NOR” Zakharevich กล่าวโดยหมายถึงประตูธรรมดาเพิ่มเติมอีกสองประตู แต่เพื่อที่จะรวมประตูต่างๆ เหล่านี้เข้าด้วยกัน พวกเขาต้องสร้างอุปกรณ์ใหม่ๆ ที่ดูดซับสัญญาณจากภายนอก และยอมให้สัญญาณอื่นๆ เลี้ยวและตัดกันโดยไม่รบกวนซึ่งกันและกัน “นั่นคือส่วนที่ยากที่สุด” Zakharevich กล่าว “การหาวิธีทำให้ทุกอย่างเข้ากันอย่างเหมาะสม” หลังจากที่เธอและฮัลล์จัดอุปกรณ์เข้าด้วยกัน พวกเขาสามารถเข้ารหัสทุกสิ่งที่ต้องการในพับกระดาษ ซึ่งแสดงให้เห็นว่า origami ทัวริงเสร็จสมบูรณ์แล้ว

คอมพิวเตอร์ origami จะไม่มีประสิทธิภาพและใช้งานไม่ได้อย่างมาก แต่โดยหลักการแล้ว หากคุณมีกระดาษแผ่นใหญ่มากและมีเวลาเหลือเฟือ คุณสามารถใช้โอริกามิเพื่อคำนวณ $latex pi$ หลายๆ หลักตามต้องการ กำหนดวิธีที่ดีที่สุดในการกำหนดเส้นทางพนักงานส่งของทุกคนในโลก หรือ รันโปรแกรมพยากรณ์อากาศ “ท้ายที่สุดแล้ว รูปแบบรอยพับก็ใหญ่โต” ฮัลล์กล่าว “พับยากแต่ก็ทำให้งานเสร็จ”

เป็นเวลาหลายทศวรรษแล้วที่นักคณิตศาสตร์สนใจการพับกระดาษโอริกามิเพราะ “มันดูสนุกและไร้ประโยชน์” กล่าว Erik Demaineนักวิทยาศาสตร์คอมพิวเตอร์จากสถาบันเทคโนโลยีแมสซาชูเซตส์ ซึ่งมีส่วนสนับสนุนคณิตศาสตร์ของ origami อย่างกว้างขวาง แต่เมื่อไม่นานมานี้ก็ได้รับความสนใจจากวิศวกรเช่นกัน

คณิตศาสตร์ของ origami ถูกนำมาใช้เพื่อออกแบบแผงโซลาร์เซลล์ขนาดใหญ่ที่สามารถพับเก็บและขนส่งไปในอวกาศได้ หุ่นยนต์ที่ว่ายในน้ำเพื่อรวบรวมข้อมูลด้านสิ่งแวดล้อม ขดลวดที่เดินทางผ่านหลอดเลือดเล็กๆ และอื่นๆ “ตอนนี้มีคนหลายร้อยหรือหลายพันคนที่ใช้คณิตศาสตร์และอัลกอริธึม origami ทั้งหมดที่เราได้พัฒนาขึ้นในการออกแบบโครงสร้างทางกลใหม่” Demaine กล่าว

ดังนั้น “ยิ่งเราทำเรื่องแบบนี้มากเท่าไหร่” ฮัลล์กล่าว “ผมคิดว่าเราจะมีโอกาสมากขึ้นในการสร้างการครอสโอเวอร์ที่ลึกซึ้งระหว่าง origami และสาขาวิชาคณิตศาสตร์ที่มีชื่อเสียง”