Cara Membuat Komputer Origami | Majalah Kuanta

Pada tahun 1936, matematikawan Inggris Alan Turing mengemukakan ide untuk komputer universal. Itu adalah perangkat sederhana: pita tak terbatas yang ditutupi angka nol dan satu, bersama dengan mesin yang bisa bergerak bolak-balik di sepanjang pita, mengubah angka nol menjadi satu dan sebaliknya sesuai dengan seperangkat aturan. Dia menunjukkan bahwa perangkat semacam itu dapat digunakan untuk melakukan perhitungan apa pun.

Turing tidak bermaksud agar idenya praktis untuk memecahkan masalah. Sebaliknya, ini menawarkan cara yang sangat berharga untuk mengeksplorasi sifat komputasi dan batasannya. Dalam beberapa dekade sejak gagasan penting tersebut, para ahli matematika telah menyusun daftar skema komputasi yang bahkan kurang praktis. Game seperti Minesweeper atau Magic: The Gathering, pada prinsipnya, dapat digunakan sebagai komputer serba guna. Begitu juga dengan apa yang disebut automata seluler seperti milik John Conway Game of Life, seperangkat aturan untuk mengembangkan kotak hitam putih pada kisi dua dimensi.

Pada bulan September 2023, Inna Zakharevich dari Universitas Cornell dan Thomas Hull dari Franklin & Marshall College menunjukkan bahwa segala sesuatu dapat dihitung dapat dihitung dengan melipat kertas. Mereka membuktikan bahwa origami adalah “Turing lengkap” — artinya, seperti mesin Turing, ia dapat menyelesaikan masalah komputasi apa pun yang mudah diselesaikan, dengan waktu yang cukup.

Zakharevich, seorang penggemar origami seumur hidup, mulai memikirkan masalah ini pada tahun 2021 setelah menemukan video yang menjelaskan kelengkapan Turing dalam Game of Life. “Saya berpikir, origami jauh lebih rumit daripada Game of Life,” kata Zakharevich. “Jika Game of Life adalah Turing yang lengkap, origami juga harusnya Turing yang lengkap.”

Tapi ini bukan bidang keahliannya. Meskipun dia telah melipat origami sejak dia masih muda — “jika Anda ingin memberi saya benda super rumit yang memerlukan selembar kertas berukuran 24 inci dan memiliki 400 langkah, saya akan mengerjakannya,” katanya — dia penelitian matematika berhubungan dengan bidang topologi aljabar dan teori kategori yang jauh lebih abstrak. Jadi dia mengirim email ke Hull, yang mempelajari matematika origami penuh waktu.

“Dia tiba-tiba mengirimi saya email, dan saya bertanya-tanya, mengapa ahli topologi aljabar bertanya kepada saya tentang hal ini?” kata Hull. Namun dia menyadari bahwa dia tidak pernah memikirkan apakah origami bisa menjadi Turing yang lengkap. “Saya pikir, mungkin memang begitu, tapi sebenarnya saya tidak tahu.”

Jadi dia dan Zakharevich berusaha membuktikan bahwa Anda bisa membuat komputer dari origami. Pertama, mereka harus menyandikan masukan dan keluaran komputasi — serta operasi logika dasar seperti AND dan OR — dalam bentuk lipatan kertas. Jika mereka kemudian dapat menunjukkan bahwa skema mereka dapat mensimulasikan beberapa model komputasi lain yang sudah dikenal sebagai Turing lengkap, mereka akan mencapai tujuan mereka.

Operasi logis mengambil satu atau lebih masukan (masing-masing ditulis sebagai TRUE atau FALSE) dan mengeluarkan keluaran (TRUE atau FALSE) berdasarkan aturan tertentu. Untuk membuat operasi kertas, para ahli matematika merancang diagram garis, yang disebut pola lipatan, yang menentukan tempat melipat kertas. Lipatan di kertas mewakili masukan. Jika Anda melipat sepanjang satu garis dalam pola lipatan, lipatannya akan terbalik ke satu sisi, menunjukkan nilai input TRUE. Namun jika Anda melipat kertas di sepanjang garis yang berbeda (berdekatan), lipatannya akan terbalik ke sisi yang berlawanan, menandakan SALAH.

Dua dari lipatan masukan ini dimasukkan ke dalam lipatan rumit yang disebut gadget. Gadget mengkodekan operasi logis. Untuk membuat semua lipatan ini dan tetap membuat kertas terlipat rata - suatu persyaratan yang diberlakukan oleh Hull dan Zakharevich - mereka menyertakan lipatan ketiga yang dipaksa untuk dilipat dengan cara tertentu. Jika lipatannya terbalik ke satu arah, berarti hasilnya BENAR. Jika dibalik, outputnya FALSE.

Para ahli matematika merancang berbagai gadget yang mengubah masukan menjadi keluaran berdasarkan berbagai operasi logika. “Itu adalah banyak bermain-main dengan kertas dan mengirimkan gambar satu sama lain … dan kemudian menulis bukti yang kuat bahwa hal-hal ini bekerja seperti yang kami katakan,” kata Hull.

Sudah diketahui sejak akhir tahun 1990an bahwa ini lebih sederhana analog satu dimensi Game of Life karya Conway sudah selesai Turing. Hull dan Zakharevich menemukan cara untuk menulis versi Kehidupan ini dalam kaitannya dengan operasi logis. “Kami akhirnya hanya perlu menggunakan empat gerbang: AND, OR, NAND dan NOR,” kata Zakharevich, mengacu pada dua gerbang sederhana tambahan. Namun untuk menggabungkan gerbang-gerbang yang berbeda ini, mereka harus membuat gadget baru yang menyerap sinyal-sinyal asing dan memungkinkan sinyal-sinyal lain berputar dan berpotongan tanpa mengganggu satu sama lain. “Itu adalah bagian tersulit,” kata Zakharevich, “mencari tahu bagaimana membuat semuanya berjalan dengan baik.” Setelah dia dan Hull berhasil memasangkan gadget mereka, mereka dapat menyandikan semua yang mereka butuhkan dalam lipatan kertas, sehingga menunjukkan bahwa origami adalah Turing yang lengkap.

Komputer origami akan sangat tidak efisien dan tidak praktis. Namun pada prinsipnya, jika Anda memiliki selembar kertas yang sangat besar dan memiliki banyak waktu luang, Anda dapat menggunakan origami untuk menghitung banyak digit $lateks pi$, menentukan cara optimal untuk mengarahkan setiap pengemudi pengiriman di dunia, atau menjalankan program untuk memprediksi cuaca. “Pada akhirnya, pola lipatannya sangat besar,” kata Hull. “Sulit untuk melipatnya, tetapi ini menyelesaikan pekerjaan.”

Selama beberapa dekade, para ahli matematika tertarik pada origami karena “kelihatannya menyenangkan dan tidak berguna,” katanya Erik Demaine, seorang ilmuwan komputer di Massachusetts Institute of Technology yang telah memberikan kontribusi besar pada matematika origami. Namun baru-baru ini hal itu juga menarik perhatian para insinyur.

Matematika origami telah digunakan untuk merancang panel surya raksasa yang dapat dilipat dan diangkut ke luar angkasa, robot yang berenang di air untuk mengumpulkan data lingkungan, stent yang berjalan melalui pembuluh darah kecil, dan banyak lagi. “Sekarang ada ratusan bahkan ribuan orang yang menggunakan semua matematika origami dan algoritma yang telah kami kembangkan dalam desain struktur mekanis baru,” kata Demaine.

Jadi, “semakin sering kita melakukan hal-hal seperti ini,” kata Hull, “semakin besar peluang kita untuk membangun persilangan mendalam antara origami dan cabang matematika yang sudah mapan.”