Tentang Automata Seluler | Permainan Kehidupan, Aturan 30, Aturan 110 & Lainnya

Empat bagian dasar

Setiap automaton seluler dibangun dari empat bagian yang sama. Kisi adalah ruang tempat sel hidup. Kisi bisa berupa garis satu dimensi, bidang dua dimensi seperti papan catur, atau bahkan ruang tiga dimensi. Keadaan adalah nilai yang bisa dimiliki sebuah sel. Dalam kasus paling sederhana, sel bersifat biner: hitam atau putih, 1 atau 0. Lingkungan tetangga adalah kumpulan sel yang secara langsung memengaruhi sebuah sel. Pada kisi persegi, biasanya ini adalah lingkungan Moore, yaitu kedelapan sel di sekelilingnya, atau lingkungan von Neumann, yaitu hanya utara, timur, selatan, dan barat. Aturan adalah otak automaton: logika yang memberi setiap sel keadaan barunya. Contohnya: jika aku hidup tetapi punya kurang dari dua tetangga hidup, aku mati kesepian. Setiap sel menerapkan aturan yang sama pada saat yang sama.

1. Permainan Kehidupan Conway

Aturan: B3/S23. Sel hidup bertahan jika punya 2 atau 3 tetangga hidup. Sel mati menjadi hidup jika punya tepat 3. Semua sel lain mati pada generasi berikutnya. John Conway merancangnya pada 1970, dan kolom Martin Gardner di Scientific American membuatnya terkenal. Permainan ini menghasilkan glider, osilator, dan pesawat antariksa. Bill Gosper menemukan senapan glider pertama pada tahun yang sama: pola yang menembakkan glider baru setiap 30 generasi, selamanya. Permainan Kehidupan dapat melakukan komputasi, karena glider dapat membawa sinyal dan bertabrakan seperti gerbang logika. Di atas segalanya, permainan ini menunjukkan perilaku rumit yang tumbuh dari aturan sederhana.

Senapan glider Gosper di Permainan Kehidupan menembakkan aliran glider diagonal — Senapan glider Gosper setelah 330 generasi. Dibuat di PictorX.

2. Aturan 30

Jenis: automaton seluler elementer satu dimensi. Keadaan berikutnya setiap sel bergantung pada dirinya dan dua tetangganya, dan setiap generasi digambar sebagai baris baru di bawah baris terakhir. Stephen Wolfram memperkenalkan Aturan 30 pada 1983. Mulailah dari satu sel hitam dan aturan ini menumbuhkan segitiga yang kacau. Ia tampak acak meski aturannya deterministik, begitu acaknya sampai kolom tengahnya pernah dipakai sebagai pembangkit bilangan acak semu. Segitiga sejenis muncul pada pigmen cangkang siput laut Conus textile.

Segitiga Aturan 30 yang tumbuh dari satu sel hitam, kacau di kanan dan bergaris di kiri — Aturan 30 dari satu sel hitam, 224 generasi. Dibuat di PictorX.

3. Aturan 110

Jenis: automaton seluler elementer satu dimensi, seperti Aturan 30, dengan tabel delapan jawaban yang berbeda. Aturan 110 terbukti universal secara komputasi: Matthew Cook menunjukkan bahwa dengan baris pertama yang sesuai, aturan ini dapat meniru komputasi apa pun yang bisa dijalankan komputer serbaguna. Aturan ini memiliki struktur bergerak yang berjalan melintasi latar yang berulang dan berinteraksi saat bertemu. Tabrakan itulah yang dipakai bukti tersebut sebagai logikanya. Aturan ini menunjukkan bagaimana aturan yang sangat sederhana dapat meniru komputasi sembarang.

Aturan 110 yang tumbuh dari satu sel di kanan, menyebar ke kiri dalam segitiga bersarang — Aturan 110 dari satu sel hitam di tepi kanan. Dibuat di PictorX.

4. Brian's Brain

Keadaan: padam, aktif (menyala), dan refrakter. Aturan: sel padam menjadi aktif jika tepat 2 tetangganya aktif. Sel aktif menjadi refrakter. Sel refrakter menjadi padam. Brian Silverman merancangnya. Karena sel harus beristirahat selama satu generasi setelah menyala, setiap denyut terus bergerak menjauh dari tempat yang sudah dilaluinya. Hasilnya adalah kerumunan pola yang bergerak sendiri, mirip gelombang dalam media yang dapat tereksitasi, seperti jaringan saraf atau otot jantung, dan sering tampak hidup dan organis.

Brian's Brain menyebar dari petak acak, sel yang menyala berwarna kuning dan jejak yang memudar berwarna ungu — Brian's Brain 70 generasi setelah petak acak, dengan jejak yang memudar. Dibuat di PictorX.

5. Wireworld

Keadaan: kosong, kepala elektron, ekor elektron, dan konduktor. Aturan: kepala menjadi ekor, ekor menjadi konduktor, dan konduktor menjadi kepala jika tepat 1 atau 2 tetangganya adalah kepala. Sel kosong tetap kosong. Brian Silverman juga merancang Wireworld, pada 1987. Sel konduktor adalah kawat, dan kepala yang diikuti ekor adalah elektron yang berjalan di sepanjang kawat itu. Wireworld dapat menyimulasikan sirkuit elektronik: lingkaran kawat dengan satu elektron adalah pembangkit detak, takik kecil adalah dioda, dan beberapa sel membentuk gerbang logika. Komputer lengkap telah dibangun di dalamnya, seperti komputer Wireworld karya David Moore dan Mark Owen yang menghitung bilangan prima.

Sirkuit Wireworld dengan dua lingkaran pembangkit detak, dua dioda, dan gerbang XOR, elektron biru dan merah di kawat kuning — Dua pembangkit detak, dua dioda, dan gerbang XOR di Wireworld. Dibuat di PictorX.

256 aturan dan empat kelas Wolfram

Sel satu dimensi dengan dua tetangga melihat salah satu dari delapan pola, dari 111 hingga 000. Sebuah aturan memberikan keadaan baru untuk masing-masing pola, jadi aturan itu terdiri atas delapan bit, dan ada 2⁸ = 256 aturan elementer. Baca kedelapan jawaban sebagai bilangan biner dan Anda mendapat nama aturannya: Aturan 30 adalah 00011110, dan Aturan 110 adalah 01101110. Stephen Wolfram mengelompokkan aturan menurut perilakunya, dari keteraturan hingga kekacauan. 1. Kelas 1 mengendap menjadi keadaan seragam. 2. Kelas 2 mengendap menjadi struktur yang stabil atau berulang. 3. Kelas 3 tetap kacau dan tampak acak, seperti Aturan 30. 4. Kelas 4 membangun struktur yang bergerak dan berinteraksi di perbatasan antara keteraturan dan kekacauan, seperti Aturan 110.

Peringkat kesulitan

Permainan Kehidupan ★☆☆☆☆ · Aturan 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Aturan 110 ★★★★★. Dua yang pertama menjelaskan dirinya sendiri saat Anda menontonnya. Aturan 110 menyembunyikan struktur bergeraknya di latar yang berulang.

Paling indah secara visual

1. Brian's Brain · 2. Permainan Kehidupan Conway · 3. Aturan 30 · 4. Aturan 110 · 5. Wireworld.

Paling penting secara matematis

1. Aturan 110, karena universalitas · 2. Permainan Kehidupan, karena universalitas dan kemunculan · 3. Aturan 30, karena kekacauan dan keacakan · 4. Wireworld, karena logika digital · 5. Brian's Brain, karena sistem yang dapat tereksitasi.

Di alam, fisika, dan kriptografi

Automata seluler dipakai untuk menyimulasikan sistem kompleks di alam, fisika, dan kriptografi. Gagasannya bermula dari Stanisław Ulam dan John von Neumann pada 1940-an, yang memakai kisi sel untuk merancang mesin yang dapat menyalin dirinya sendiri. Di dunia nyata, Anda dapat melihat automata seluler pada pigmen beberapa cangkang, seperti Conus textile, yang segitiganya mirip Aturan 30, dan pada sisik kadal permata (Timon lepidus), yang berganti antara hijau dan hitam menurut aturan yang mendekati automaton seluler. Fisikawan memakainya untuk memodelkan aliran gas, tumpukan pasir, dan kebakaran hutan. Keacakan yang tampak pada Aturan 30 menjadikannya kandidat untuk pembangkit bilangan acak dan sandi aliran.

Jelajahi di PictorX

Buka Automata Seluler untuk menjalankan kelimanya. Saksikan senapan glider, armada pesawat antariksa, atau R-pentomino, yang butuh 1.103 generasi untuk stabil. Ketik aturan Permainan Kehidupan apa pun seperti B36/S23, atau nomor aturan elementer apa pun dari 0 hingga 255. Gambar dan hapus sel, kirim elektron melalui sirkuit Wireworld, sambungkan tepi, dan beralih ke mode warna-warni. Simpan PNG atau buka kanvas di editor PictorX.

Pertanyaan yang sering diajukan

Apa itu automaton seluler?

Kisi berisi sel yang masing-masing punya keadaan. Pada setiap detak, semua sel diperbarui bersamaan dengan satu aturan tetap yang hanya melihat sebuah sel dan tetangganya. Meski aturannya sederhana, polanya bisa rumit dan tak terduga.

Siapa penemu automata seluler?

Stanisław Ulam dan John von Neumann, pada 1940-an di Los Alamos. Permainan Kehidupan karya John Conway (1970) mempopulerkan gagasan ini, dan Stephen Wolfram mempelajari 256 aturan elementer pada 1980-an.

Automata seluler mana yang Turing-lengkap?

Di antara lima automaton di sini, Aturan 110 dan Permainan Kehidupan terbukti universal, dan Wireworld dapat memuat komputer lengkap. Universal berarti, dengan pola awal yang tepat, automaton itu dapat menjalankan komputasi apa pun yang bisa dilakukan komputer serbaguna.

Apa empat kelas Wolfram?

Kelas 1 meredup menjadi keadaan seragam, kelas 2 mengendap menjadi struktur yang stabil atau berulang, kelas 3 tetap kacau seperti Aturan 30, dan kelas 4 membangun struktur yang bergerak dan saling berinteraksi seperti Aturan 110.

Mengapa Aturan 30 tampak acak?

Setiap langkahnya pasti, tetapi setiap sel mencampur tetangga kirinya dengan dua sel lainnya dengan cara yang cepat menyebarkan perbedaan kecil. Belum ada pola sederhana yang ditemukan di kolom tengahnya, itulah sebabnya kolom itu dipakai untuk membuat bilangan acak.