Get best of the week

Menghasilkan angka pseudo-acak menggunakan automaton seluler: Aturan 30

Generator nomor pseudorandom memberikan angka secara deterministik, tetapi biasanya angka-angka ini terlihat non-periodik (acak). Paling tidak dalam banyak kasus, penggunaan angka seperti itu biasanya terjadi. Generator mengambil nilai awal (idealnya angka acak sejati) dan menghasilkan urutan angka, berfungsi sebagai fungsi dari nilai awal dan / atau angka sebelumnya dalam urutan. Angka-angka tersebut adalah pseudo-acak (dan bukan angka acak sejati) karena fakta bahwa jika nilai awal yang diteruskan ke generator diketahui, angka-angka ini dapat dihasilkan lagi secara algoritmik. Angka acak yang sebenarnya dihasilkan menggunakan perangkat keras khusus atau fenomena fisik tertentu - fluktuasi pulsa dalam volume darah, tekanan atmosfer, kebisingan termal, proses kuantum, dan sebagainya.



Ada banyak cara untuk menghasilkan angka acak semu. Misalnya, algoritma Blum - Blum - Shub , metode kuadrat rata-rata , metode Fibonacci dengan penundaan . Hari ini kita akan berbicara tentang menghasilkan angka acak menggunakan Aturan 30 , yang menggunakan pendekatan ambigu yang melibatkan penggunaan model otomat seluler . Metode ini melewati banyak tes angka acak standar dan digunakan dalam Mathematica untuk menghasilkan bilangan bulat acak.

Otomat seluler


Sebelum kita membahas Subjek Rule 30, mari kita luangkan waktu dalam automata seluler. Otomat seluler adalah model diskrit yang terdiri dari kisi-kisi sel reguler dari dimensi apa pun. Masing-masing sel kisi dapat berada di salah satu set keadaan terbatas. Selain itu, untuk setiap sel, konsep seperti "lingkungan" didefinisikan. Di sekitar sel tertentu, misalnya, semua sel yang berada pada jarak tidak lebih dari 2 darinya dapat masuk. Ada aturan yang menentukan bagaimana sel berinteraksi satu sama lain dan beralih ke generasi berikutnya (negara bagian). Aturan-aturan ini terutama diwakili oleh fungsi matematika (dapat diprogram), yang tergantung pada keadaan sel saat ini dan pada keadaan tetangga mereka.


Deskripsi otomat seluler

Deskripsi otomat seluler dari gambar sebelumnya memungkinkan Anda mengetahui bahwa setiap sel dapat berada dalam salah satu dari dua status akhir -0(ditunjukkan dengan warna merah) dan1(ditampilkan dalam warna hitam). Setiap sel masuk ke generasi berikutnya, mengambil status baru yang dihasilkan dari penerapan operasiXORke 8 tetangganya. Generasi pertama (keadaan awal) dari kisi diatur secara acak. Pengoperasian otomat seluler ini ditunjukkan di bawah ini.




Otomat seluler berbasis XOR beraksi Gagasan tentang otomat seluler muncul pada tahun 1940-an berkat Stanislav Ulam dan John von Neumann . Automata seluler telah menemukan aplikasi dalam ilmu komputer, matematika, fisika, dalam teori sistem yang kompleks, dalam biologi teoritis, dan dalam masalah pemodelan struktur mikro media dan bahan. Pada 1980-an, Stephen Wolfram melakukan studi sistematis otomat seluler satu dimensi (juga disebut otomat seluler elementer), yang menjadi dasar Peraturan 30.

Aturan 30


Aturan 30 adalah otomat seluler elementer (satu dimensi) di mana setiap sel dapat berada di salah satu dari dua keadaan akhir: 0(sel merah pada gambar di bawah) dan 1(sel hitam). Sekitar sel diwakili oleh dua tetangga terdekatnya yang terletak di sebelah kiri dan kanannya. Keadaan berikutnya (generasi) sel tergantung pada keadaan saat ini dan pada keadaan tetangga-tetangganya. Aturan untuk mentransisikan sel ke status berikutnya ditunjukkan pada gambar berikut.


Aturan 30 Aturan

-aturan transisi ini ke keadaan sel yang baru dapat disederhanakan ditulis sebagaileft XOR (central OR right).

Kami mengeluarkan sel-sel automaton dalam bentuk kisi dua dimensi, yang setiap barisnya mewakili satu generasi (keadaan). Ketika generasi (keadaan) sel selanjutnya dihitung, ini ditampilkan di bawah kondisi terakhir yang diketahui. Setiap baris berisi jumlah sel yang terbatas, pada akhirnya, "loop".


Aturan 30 dalam aksi

Pola di atas muncul dari keadaan awal (baris 0) ketika satu sel memiliki keadaan1(hitam) dan semua sel di sekitarnya memiliki keadaan0(merah). Keadaan sel dalam generasi berikutnya (baris 1) dihitung sesuai dengan aturan di atas. Kotak vertikal mewakili waktu, dan persimpangan baris dan kolom mewakili keadaan sel tertentu pada tahap tertentu dalam pengembangan sistem.


Generasi t dan generasi t + 1

Saat pola berkembang, segitiga merah dengan ukuran berbeda sering muncul di dalamnya, tetapi, secara umum, pola yang dapat dibedakan tidak dapat dikenali dalam struktur yang dihasilkan. Fragmen kisi di atas dibuat pada saat yang dipilih secara sewenang-wenang. Di sini Anda dapat melihat kekacauan dan aperiodisitas. Properti ini adalah Aturan 30 dan digunakan untuk menghasilkan angka pseudo-acak.

Pembuatan Angka Acak Semu


Seperti yang telah disebutkan, Aturan 30 menunjukkan perilaku aperiodik dan kacau. Akibatnya, penerapannya mengarah pada penciptaan kompleks, dan, tampaknya, pola acak menurut aturan sederhana dan jelas. Untuk menghasilkan angka acak menggunakan Aturan 30, kolom kisi pusat digunakan, dari mana urutan nbit acak dipilih , dari mana nangka acak -bit yang diinginkan dihasilkan . Angka acak berikutnya dihasilkan menggunakan nbit - bit berikut dari kolom.


Menghasilkan angka acak menggunakan Aturan 30

Jika Anda selalu mulai memilih sel dari baris pertama, maka urutan angka yang dihasilkan akan selalu dapat diprediksi. Dan ini bukan yang kita butuhkan. Untuk membuat angka pseudorandom, kami akan menggunakan nilai awal acak (misalnya, waktu saat ini), lewati jumlah baris yang sesuai, dan setelah itu pilih urutan darinbaris dan buat angka acak berdasarkan pada mereka.

Angka pseudo-acak yang dihasilkan menggunakan Aturan 30 tidak aman secara kriptografis, tetapi cocok untuk simulasi - sampai kita menggunakan nilai awal yang tidak sesuai seperti0.

Salah satu keuntungan utama penerapan Aturan 30 untuk menghasilkan angka pseudo-acak adalah bahwa Anda dapat membuat banyak angka acak dalam mode paralel dengan secara acak memilih banyak kolom dengan panjang n bit. Berikut adalah contoh dari urutan pseudo-acak nomor 8-bit yang dihasilkan oleh metode ini menggunakan nilai awal 0: 220, 197, 147, 174, 117, 97, 149, 171, 240, 241.

Nilai awal, di samping itu, dapat digunakan untuk mengatur keadaan awal model (baris No. 0). Akibatnya, angka pseudo-acak dapat diperoleh hanya dengan memilihnbit dari kolom tengah, mulai dari baris nol. Pendekatan ini lebih efektif, tetapi sangat tergantung pada kualitas nilai awal. Nilai awal yang tidak dipilih dengan benar dapat menyebabkan penampilan angka yang diprediksi dengan baik. Peragaan pendekatan ini dapat ditemukan di sini .

Aturan 30 di dunia nyata


Aturan 30 dapat dilihat di alam, dalam bentuk pola pada cangkang dari spesies gastropoda tekstil Conus . Stasiun kereta Cambridge North dibingkai oleh panel yang menggambarkan hasil evolusi dari model yang dibangun menggunakan Peraturan 30.

Ringkasan


Jika Anda menemukan Aturan 30 menarik, saya sarankan menulis simulasi Anda sendiri menggunakan p5 library . Algoritma ini dapat diimplementasikan dalam bentuk yang cukup umum, yang akan memungkinkan program yang sama untuk menghasilkan pola untuk aturan yang berbeda - 90, 110, 117, dan seterusnya. Pola yang dihasilkan menggunakan berbagai aturan sangat menarik. Jika mau, Anda bisa naik ke level selanjutnya. Anda dapat memperluas model menjadi tiga dimensi dan menjelajahi evolusi pola. Saya pikir pemrograman dapat membawa banyak kesenangan jika memiliki komponen visual.

Sungguh menakjubkan ketika dua bidang ilmu yang tampaknya tidak berhubungan, automata seluler dan kriptografi, bergabung untuk menciptakan sesuatu yang mengejutkan. Meskipun algoritma yang dijelaskan di sini tidak lagi banyak digunakan karena munculnya algoritma yang lebih efisien, itu mendorong kita untuk secara kreatif menggunakan automata seluler.

Pembaca yang budiman! Apa generator nomor acak semu yang Anda gunakan?

More articles:


All Articles