RANK DARI GRUP AUTOMATA SELULER BERHINGGA BERDIMENSI SATU

LINGGA GITA D, Dr. Yeni Susanti, M.Si.;Dr. Budi Surodjo, M.Si.

2018 | Tesis | MAGISTER MATEMATIKA

Automata seluler adalah transformasi atas sebarang himpunan konfigurasi sedemikian sehingga peta dari setiap sel pada universe hanya ditentukan oleh pemetaan lokal, yaitu pemetaan dari himpunan konfigurasi ke alfabet dengan domain pada himpunan konfigurasi direstriksi ke suatu himpunan bagian berhingga tak kosong dari universe. Pada tesis ini dibahas mengenai konsep automata seluler dan hubungannya dengan teori grup. Himpunan semua automata seluler atas grup G dan alfabet A, dinotasikan dengan CA(G;A), terhadap operasi komposisi fungsi membentuk semigrup dengan identitas. Lebih lanjut, automata seluler yang invertibel atas grup G dan alfabet A adalah automata seluler Tau anggota dari CA(G;A) sedemikian sehingga Tau bijektif dan Tau invers anggota dari CA(G;A). Himpunan semua automata seluler yang invertibel atas grup G dan alfabet A, dinotasikan dengan ICA(G;A), terhadap operasi komposisi fungsi membentuk grup. Selanjutnya, pada tesis ini diselidiki rank dari grup ICA(Z_n;A), yaitu grup automata seluler berhingga atas grup Z_n dan alfabet berhingga A. Lebih khusus, diselidiki rank dari grup ICA(Z_n;A), untuk n=p, n=2^k, atau n=2^kp, dengan p bilangan prima dan k>=1 bilangan bulat.

A cellular automaton is a transformation of the set of all configurations such that the image of any cell in the universe is determined by a local function, that is a function from the set of all configurations to alphabet with the domain in its set of all configurations is restricted to any finite nonempty subset of the universe. In this thesis, we discuss the theory of cellular automata and its relationship with group theory. Under the composition of functions, the set of all cellular automata over group G and alphabet A, denoted by CA(G;A), is a semigroup with identity. Furthermore, an invertible cellular automaton over group G and alphabet A is a cellular automaton Tau in CA(G;A) such that Tau is bijective and Tau inverse in CA(G;A). Under the composition of functions, the set of all invertible cellular automata over group G and alphabet A, denoted by ICA(G;A), is a group. Furthermore, in this thesis, we investigate the rank of the group ICA(Z_n;A), that is the group of cellular automata over group Z_n and a finite alphabet A. In particular, we investigate the rank of the group ICA(Z_n;A) when n=p, n=2^k, or n=2^kp, for any prime p and any integer k>=1.

Kata Kunci : Automata seluler, grup berhingga, himpunan pembangun terkecil.