Cách làm một chiếc máy tính Origami | Tạp chí Quanta

Năm 1936, nhà toán học người Anh Alan Turing nảy ra ý tưởng về một chiếc máy tính đa năng. Đó là một thiết bị đơn giản: một dải băng vô tận được bao phủ bởi các số XNUMX và số XNUMX, cùng với một chiếc máy có thể di chuyển qua lại dọc theo băng, thay đổi số XNUMX thành số XNUMX và ngược lại theo một số quy tắc. Ông đã chỉ ra rằng một thiết bị như vậy có thể được sử dụng để thực hiện bất kỳ tính toán nào.

Turing không có ý định biến ý tưởng của mình thành hiện thực để giải quyết vấn đề. Đúng hơn, nó đưa ra một cách vô giá để khám phá bản chất của tính toán và các giới hạn của nó. Trong nhiều thập kỷ kể từ ý tưởng có ảnh hưởng sâu sắc đó, các nhà toán học đã đưa ra một danh sách các sơ đồ tính toán thậm chí còn ít thực tế hơn. Về nguyên tắc, các trò chơi như Minesweeper hoặc Magic: The Gathering có thể được sử dụng làm máy tính đa năng. Vì vậy, có thể có cái gọi là máy tự động di động như của John Conway Trò chơi của cuộc sống, một bộ quy tắc để phát triển các hình vuông màu đen và trắng trên lưới hai chiều.

Vào tháng Chín 2023, Inna Zakharevich của Đại học Cornell và Thomas Hull của Franklin & Marshall College đã chỉ ra rằng bất cứ thứ gì có thể tính toán được có thể tính được bằng cách gấp giấy. Họ đã chứng minh rằng origami là “Turing hoàn chỉnh” - nghĩa là, giống như máy Turing, nó có thể giải quyết mọi vấn đề tính toán dễ xử lý, nếu có đủ thời gian.

Zakharevich, một người đam mê origami suốt đời, bắt đầu nghĩ đến vấn đề này vào năm 2021 sau khi tình cờ xem được một video giải thích tính hoàn chỉnh Turing của Trò chơi cuộc sống. Zakharevich nói: “Tôi nghĩ rằng origami phức tạp hơn nhiều so với Trò chơi cuộc sống. “Nếu Trò chơi Cuộc sống đã hoàn thành Turing thì origami cũng sẽ hoàn thành Turing.”

Nhưng đây không phải là lĩnh vực chuyên môn của cô. Mặc dù cô ấy đã gấp origami từ khi còn nhỏ - “nếu bạn muốn đưa cho tôi một thứ siêu phức tạp đòi hỏi một tờ giấy 24 inch và có 400 bước, thì tôi đều làm được điều đó,” cô ấy nói - cô ấy nghiên cứu toán học đề cập đến các lĩnh vực trừu tượng hơn nhiều của cấu trúc liên kết đại số và lý thuyết phạm trù. Vì vậy, cô đã gửi email cho Hull, người đang nghiên cứu toán origami toàn thời gian.

“Cô ấy vừa bất ngờ gửi email cho tôi, và tôi nghĩ, tại sao một nhà tôpô đại số lại hỏi tôi về điều này?” Hull nói. Nhưng anh nhận ra rằng anh chưa bao giờ thực sự nghĩ đến việc liệu origami có thể là Turing hoàn chỉnh hay không. “Tôi nghĩ, có lẽ là vậy, nhưng tôi thực sự không biết.”

Vì vậy, anh ấy và Zakharevich bắt đầu chứng minh rằng bạn có thể tạo ra một chiếc máy tính từ origami. Đầu tiên, họ phải mã hóa đầu vào và đầu ra tính toán - cũng như các phép toán logic cơ bản như AND và OR - dưới dạng các nếp gấp giấy. Nếu sau đó họ có thể chứng minh rằng sơ đồ của họ có thể mô phỏng một số mô hình tính toán khác đã được biết đến là Turing hoàn chỉnh, thì họ sẽ hoàn thành được mục tiêu của mình.

Một phép toán logic nhận một hoặc nhiều đầu vào (mỗi đầu vào được viết là TRUE hoặc FALSE) và tạo ra một đầu ra (TRUE hoặc FALSE) dựa trên một quy tắc nhất định. Để thực hiện một thao tác trên giấy, các nhà toán học đã thiết kế một sơ đồ các đường thẳng, gọi là mẫu nếp gấp, để xác định vị trí gấp tờ giấy. Một nếp gấp trên tờ giấy tượng trưng cho một đầu vào. Nếu bạn gấp dọc theo một đường trong mẫu gấp, nếp gấp sẽ lật sang một bên, biểu thị giá trị đầu vào là TRUE. Nhưng nếu bạn gấp tờ giấy dọc theo một đường khác (gần đó), nếp gấp sẽ lật sang phía đối diện, biểu thị SAI.

Hai trong số những nếp gấp đầu vào này tạo thành một loạt các nếp gấp phức tạp được gọi là tiện ích. Tiện ích mã hóa hoạt động logic. Để thực hiện tất cả các nếp gấp này mà vẫn có thể gấp phẳng tờ giấy - một yêu cầu mà Hull và Zakharevich đặt ra - họ đã đưa vào nếp gấp thứ ba buộc phải gấp theo một cách cụ thể. Nếu nếp gấp lật một chiều, điều đó có nghĩa là đầu ra là TRUE. Nếu nó lật ngược lại thì kết quả là FALSE.

Các nhà toán học đã thiết kế các tiện ích khác nhau để biến đầu vào thành đầu ra theo các phép toán logic khác nhau. Hull nói: “Có rất nhiều việc phải loay hoay với giấy và gửi ảnh cho nhau… rồi viết ra những bằng chứng nghiêm ngặt rằng những thứ này hoạt động theo cách mà chúng tôi đã nói.

Người ta đã biết từ cuối những năm 1990 rằng một cách đơn giản hơn tương tự một chiều Trò chơi cuộc sống của Conway đã hoàn thành Turing. Hull và Zakharevich đã tìm ra cách viết phiên bản Cuộc sống này bằng các phép toán logic. “Cuối cùng, chúng tôi chỉ cần sử dụng bốn cổng: AND, OR, NAND và NOR,” Zakharevich nói, đề cập đến hai cổng đơn giản bổ sung. Nhưng để kết hợp các cổng khác nhau này, họ phải chế tạo các thiết bị mới có khả năng hấp thụ các tín hiệu không liên quan và cho phép các tín hiệu khác chuyển hướng và giao nhau mà không gây nhiễu lẫn nhau. “Đó là phần khó nhất,” Zakharevich nói, “tìm ra cách sắp xếp mọi thứ một cách hợp lý.” Sau khi cô và Hull cố gắng ghép các thiết bị của họ lại với nhau, họ có thể mã hóa mọi thứ họ cần vào các nếp gấp giấy, qua đó cho thấy rằng origami đã hoàn thành Turing.

Một chiếc máy tính origami sẽ rất kém hiệu quả và không thực tế. Nhưng về nguyên tắc, nếu bạn có một tờ giấy rất lớn và có nhiều thời gian trong tay, bạn có thể sử dụng origami để tính tùy ý nhiều chữ số của $latex pi$, xác định cách tối ưu để định tuyến mọi tài xế giao hàng trên thế giới, hoặc chạy một chương trình để dự đoán thời tiết. Hull nói: “Cuối cùng, kiểu nếp gấp rất lớn. “Thật khó để gấp lại, nhưng nó hoàn thành công việc.”

Trong nhiều thập kỷ, các nhà toán học bị thu hút bởi origami vì “nó có vẻ thú vị và vô dụng”, cho biết. Erik Demaine, một nhà khoa học máy tính tại Viện Công nghệ Massachusetts, người đã đóng góp rất nhiều cho toán học về origami. Nhưng gần đây nó cũng đã lọt vào mắt xanh của các kỹ sư.

Toán học origami đã được sử dụng để thiết kế các tấm pin mặt trời khổng lồ có thể gấp lại và vận chuyển vào không gian, robot bơi trong nước để thu thập dữ liệu môi trường, ống đỡ động mạch di chuyển qua các mạch máu nhỏ, v.v. Demaine nói: “Bây giờ có hàng trăm, nếu không muốn nói là hàng nghìn người sử dụng tất cả các phép toán và thuật toán origami mà chúng tôi đã phát triển để thiết kế các cấu trúc cơ khí mới”.

Và vì vậy, “chúng ta càng làm những thứ như thế này nhiều,” Hull nói, “tôi nghĩ chúng ta sẽ có cơ hội tốt hơn để thiết lập sự giao thoa sâu sắc giữa origami và các nhánh toán học lâu đời.”