'Permainan Kehidupan' Matematika Mengungkapkan Pola Pengulangan yang Telah Lama Dicari | Majalah Kuanta

Pada tahun 1969, ahli matematika Inggris John Conway merancang seperangkat aturan sederhana yang menakjubkan untuk menciptakan perilaku kompleks. Game of Life-nya, yang sering disebut sebagai Kehidupan, terbentang di sel-sel persegi yang tak terbatas. Setiap sel bisa “hidup” atau “mati”. Grid berevolusi melalui serangkaian putaran (atau “generasi”), dengan nasib setiap sel ditentukan oleh delapan sel yang mengelilinginya. Aturannya adalah sebagai berikut:

1. Kelahiran: Sebuah sel mati dengan tepat tiga tetangga yang hidup menjadi hidup.
2. Kelangsungan Hidup: Sebuah sel hidup dengan dua atau tiga tetangga yang hidup tetap hidup.
3. Kematian: Sebuah sel hidup dengan kurang dari dua atau lebih dari tiga tetangga hidup akan mati.

Aturan sederhana ini menciptakan beragam pola, atau “bentuk kehidupan”, yang berevolusi dari berbagai kemungkinan konfigurasi awal grid. Para pecinta permainan telah menghitung dan membuat taksonomi pola-pola ini dengan cara yang terus berkembang katalog online. Conway menemukan pola yang disebut penutup mata, yang berosilasi di antara dua keadaan.

Tahun berikutnya, ia menemukan pola yang jauh lebih rumit yang disebut pulsar, yang berosilasi di antara tiga keadaan berbeda.

Segera setelah osilator ditemukan, para penjelajah awal permainan bertanya-tanya apakah ada osilator di setiap periode. “Awalnya, kami hanya melihat periode 1, 2, 3, 4 dan 15,” kata pemrogram komputer dan matematikawan Bill Gosper, yang kemudian menemukan 17 osilator baru yang berbeda selama beberapa dekade berikutnya. Osilator periode 15 (ditunjukkan di bawah) sangat sering muncul dalam pencarian acak.

Kejutan mengintai bagi mereka yang ingin menemukannya. “Dari pengamatan berjam-jam dan berhari-hari, periode 5 sepertinya mustahil,” kata Gosper. Kemudian pada tahun 1971, dua tahun setelah permainan itu ditemukan, sebuah permainan ditemukan. Perburuan osilator baru tumbuh menjadi fokus utama permainan, sebuah pencarian yang didukung oleh kemajuan teknologi komputer. Kisah pencarian rahasia yang dilakukan pada komputer kantor telah menjadi landasan cerita rakyat permainan ini. “Jumlah waktu komputer yang dicuri dari mainframe perusahaan dan universitas sangatlah mengejutkan,” kata Gosper.

Sepanjang tahun 1970-an, para matematikawan dan penghobi mengisi periode-periode pendek lainnya dan menemukan periode-periode yang lebih panjang. Akhirnya, ahli matematika menemukan cara sistematis untuk membangun osilator jangka panjang. Namun osilator dengan periode antara 15 dan 43 terbukti sulit ditemukan. “Orang-orang telah mencoba mencari tahu titik tengahnya selama bertahun-tahun,” kata Maya Karpovich, seorang mahasiswa pascasarjana di Universitas Maryland. Mengisi kekosongan tersebut memaksa para peneliti untuk memimpikan serangkaian teknik baru yang mendorong batas-batas dari apa yang dianggap mungkin dilakukan dengan automata seluler, sebagaimana para ahli matematika menyebut jaringan yang berevolusi seperti Kehidupan.

Kini Karpovich dan enam rekan penulis telah mengumumkan dalam a pracetak Desember bahwa mereka telah menemukan dua periode terakhir yang hilang: 19 dan 41. Dengan terisinya celah tersebut, Kehidupan sekarang dikenal sebagai “omniperiodik” — sebutkan bilangan bulat positif, dan terdapat pola yang berulang setelah beberapa langkah tersebut.

Komunitas berkembang yang mengabdikan diri untuk mempelajari Kehidupan, yang mencakup banyak ahli matematika riset tetapi juga banyak penghobi, tidak hanya menemukan osilator tetapi semua jenis pola baru. Mereka telah menemukan pola-pola yang berjalan melintasi grid, yang disebut pesawat ruang angkasa, dan pola-pola yang membangun pola-pola lain: senjata, konstruktor, dan peternak. Mereka menemukan pola yang menghitung bilangan prima, dan bahkan pola yang dapat mengeksekusi algoritma rumit yang sewenang-wenang.

Osilator dengan periode lebih pendek dari 15 dapat ditemukan secara manual atau dengan algoritma dasar yang mencari osilator satu sel dalam satu waktu. Namun seiring dengan bertambahnya jangka waktu, kompleksitasnya juga meningkat, sehingga penelusuran brute-force menjadi kurang efektif. “Untuk periode kecil, Anda dapat mencari secara langsung,” kata Matthias Merzenich, salah satu penulis makalah baru yang menemukan osilator periode-31 pertama pada tahun 2010. “Tetapi Anda tidak bisa lebih dari itu. Anda tidak bisa hanya memilih periode dan mencarinya.” (Merzenich memperoleh gelar doktor dalam bidang matematika dari Oregon State University pada tahun 2021, tetapi saat ini bekerja di sebuah pertanian.)

Pada tahun 1996, David Buckingham, seorang konsultan komputer lepas Kanada dan penggila kehidupan yang telah mencari pola sejak akhir tahun 1970an, menunjukkan bahwa osilator periode 61 dan lebih tinggi dapat dibuat dengan mengirimkan pola di sekitar jalur tertutup dalam putaran tanpa akhir. . Dengan mengontrol panjang putaran - dan waktu yang dibutuhkan pola untuk menyelesaikan satu putaran - Buckingham menemukan bahwa dia dapat membuat periode tersebut sebesar yang dia suka. “Ini chemistry tanpa bau aneh atau pecahan kaca,” katanya. “Seperti membangun senyawa dan kemudian mengeksplorasi interaksi di antara mereka.” Ini berarti bahwa, dalam satu kesempatan, dia telah menemukan cara untuk membuat osilator dengan periode yang sangat panjang, asalkan lebih panjang dari 61.

Terdapat banyak hasil pada pertengahan tahun 1990an, ketika banyak dari osilator yang hilang antara 15 dan 61 ditemukan melalui kombinasi kreatif dari osilator yang dikenal, yang telah diberi nama yang berwarna-warni. Katering dipadukan dengan lampu lalu lintas, gunung berapi mengeluarkan percikan api, dan pemakan memakan pesawat layang.

Pada pergantian abad ke-21, hanya selusin periode yang masih beredar. “Tampaknya sangat mungkin untuk menyelesaikan masalah ini,” kata Merzenich. Pada tahun 2013, penemuan baru yang disebut loop Snark menyempurnakan teknik Buckingham tahun 1996 dan menurunkan batas yang di atasnya mudah untuk membuat osilator dari 61 menjadi 43. Hal ini hanya menyisakan lima periode yang hilang. Satu lagi ditemukan pada tahun 2019, dan dua lagi pada tahun 2022, sehingga hanya menyisakan 19 dan 41 — keduanya bilangan prima. “Bilangan prima lebih sulit karena Anda tidak dapat menggunakan osilator berperiode kecil untuk membangunnya,” kata Merzenich.

Mitchell Riley, peneliti postdoctoral di New York University Abu Dhabi dan salah satu penulis makalah baru ini, telah lama tertarik dengan jenis osilator yang disebut pengganggu. “Cara kerja para pengganggu adalah, Anda memiliki pola aktif di tengah dan beberapa hal stabil di luar yang bereaksi dengannya,” jelas Riley. Benda stabil, yang disebut katalis, berfungsi untuk mendorong pola aktif kembali ke keadaan semula.

Mendesainnya itu sulit. “Semua pola ini sangat rapuh,” kata Riley. “Jika Anda meletakkan satu titik di luar tempatnya, biasanya titik tersebut akan meledak.”

Riley membuat program bernama Barrister untuk mencari katalis baru. “Apa yang kami cari adalah benda mati yang kuat. Intinya adalah kami ingin mereka berinteraksi dengan apa yang terjadi di tengah dan kemudian pulih,” kata Riley.

Riley memasukkan katalis yang ditemukan Barrister ke dalam program pencarian lain yang memasangkannya dengan pola aktif. Hal ini sebagian besar menyebabkan kegagalan, katanya. “Sangat jarang salah satu katalis ini bertahan dalam interaksi. Tidak ada jaminan kesuksesan. Anda hanya berharap dan berharap mendapatkan jackpot. Rasanya seperti berjudi.”

Akhirnya, taruhannya terbayar. Setelah beberapa kali nyaris meleset – dan modifikasi pada kode yang memperluas pencarian hingga mencakup pola simetris – ia menemukan interaksi katalis yang dapat menopang osilator periode-19. “Orang-orang telah mencoba segala macam pencarian yang sangat rumit dengan banyak katalis dan banyak hal aktif yang langka di tengah-tengahnya, namun yang diperlukan hanyalah menemukan katalis baru yang besar ini,” kata Riley.

Periode terakhir yang hilang, 41, ditemukan oleh Nicolo Brown, rekan penulis lainnya, yang masih menjadi sarjana matematika di Universitas California, Santa Cruz. Brown menggunakan pesawat layang sebagai katalis, sebuah ide yang pertama kali diajukan oleh Merzenich.

“Kami telah menemukan begitu banyak perilaku mendalam selama 10 tahun terakhir,” kata Karpovich. “Semua orang merayakannya selama seminggu – dan kemudian beralih ke hal lain. Masih banyak masalah lain yang harus diselesaikan.” Bisakah osilator pada periode tertentu dibuat lebih kecil? Bisakah osilator ditemukan di mana setiap sel berosilasi? Bisakah senjata dibuat dengan jangka waktu tertentu? Bisakah pesawat luar angkasa dibuat untuk melakukan perjalanan dengan kecepatan tertentu?

Seperti yang dikatakan Buckingham, “Rasanya seperti menjadi anak-anak di toko mainan yang tak ada habisnya.”