Classes of complexity of uni- and bidimensional cellular automaton and properties of Boolean functions

Classes of complexity of uni- and bidimensional cellular automaton

and properties of Boolean functions

For a Boolean function with n variables (n > 0) it is the possibility of non-effective dependence by a precise variable of this function and in this case the dependence of this function by the variable is redundant (fictitious). The constant and the variable are functions with redundant (fictitious) variables. A hierarchy of fictive dependencies is obtained in the FBⁿ set (the set of Boolean functions with n variables). This hierarchy is put in correlation with the above classification of functions (with effective / fictitious variables) and is refined according to threshold i of a Boolean function of n variables, with integer i, i I[0,2^n-1] The results are extended to the classes of trivalent functions and there are the pre-requisites to become general for other orders of multivalent logical functions.

The representation by threshold contribute to a refined classification of Boolean functions and to inaugurate some cryptographic techniques based on logical methods, not on digital methods.

We adopted the definition of simple CA, first for the uni-dimensional case, second for the bidimensional case with the neighbourhouses Von Neumann and Moore.

In primul rind, vom opera o partitie intre AC in functie de regula (sau regulile) care se aplica de un numar infinit de ori din pas in pas si vom definit AC cu tablou alb (128 la numar), cu tablou negru (64 la numar) si cu tablou mixt (64 la numar).Esenta acestei lucrari consta in doua teoreme care constituie baza unei partitii intre clasele de automate celulare AC₁ si AC₂, pe de o parte, si AC₃ si AC₄ , pe de alta. Un prim rezultat (care se aplica unui numar de 38 de automate celulare unidimensionale) statueaza faptul ca daca regula unui AC are cel putin o variabila fictiva, el este de clasa AC₁ sau AC₂. Rezulta, deci, ca toate AC de clasa AC₃ sau AC₄ au in regula numai variabile efective. Un al doilea rezultat (care se aplica unui numar de 60 de automate celulare unuidimensionale) stabileste faptul ca daca pragul functiei booleene care reprezinta regula este 0, 1 sau 2, atunci AC respectiv este de clasa AC₀ si AC₁ (doar cu trei exceptii de AC, exceptii bine motivate). Rezulta imediat ca toate AC de clasa AC₂ sau AC₃ au ca regula o functie booleeana de prag 3 sau 4.

First we will operate a partition between cellular automaton (CA) depended on rule (or rules) which applied step by step an infinit number of times and we will define CA with white table (half of all, in number of 128 ), with black table (64 in all) and with gray table (64 in all). The core of this paper consists in two theorems which constitute the base of une partition between the cellular automaton of CA₁ si CA₂, on the one hand, and CA₃ si CA₄, on the other hand. A prime result (which is valid for a number of 38 unidimensional cellular automaton) set the following fact: if the rule of a CA have at lest a fictitious variable, then the CA belongs to CA₁ or CA₂ classes. It result that all CA of CA₃ or CA₄ class have a rule which, interpreted as a function, have only effective variabiles. An another result (which is valid for a number of 60 of unuidimensional cellular automaton) set the following fact: if the thresould of the Boolean function which represents the rule is 0, 1 or 2, then the respectiv CA belongs of AC₁ or AC₂ classes (excepting three CA, good motivated exceptions). It result directly that all CA of CA₃ or CA₄ class have a rule which, interpreted as a function, have the thresould 3 or 4.

1. Efective variabies and fictious variables in the Bolean functions. Threshoulds of Booleean functions

Variabilele sau functiile booleene elementare, iⁿ_p, cu n > 0 si p I 0,n-1], numar intreg, sint riguros determinate de cei doi parametri, superior si inferior. Daca vom neglija parametrul superior, deci vom scrie 'x₁', de exemplu, vom fi in posesia unei reprezentari vagi, caci reprezentarea [x₁] se poate intinde pe orice lungime de tip 2ⁿ, cu n luind valori de la 1 incolo. Aceeasi ambiguitate de reprezentare persista si in cazul tautologiei si contradictiei totale, functii care nu depind efectiv de nici o variabila, dar pot fi reprezentate ca functii de oricite variabile (toate redundante).

Deci precizarea clasei FBⁿ careia ii apartine functia f devine esentiala. Vom introduce in continuare notiunea de variabila efectiva (esentiala) a unei functii fata de o variabila in contradictie cu notiunea de variabila redundanta (neesentiala, fictiva).

In prealabil, vom reprezenta variabilele x_p prin (iⁿ_p),

(iⁿ_p) = ((1*2^(n-p-1))(0*2^(n-p-1))*2^p

cu p I [0,n-1], numar intreg (prin ' ' reprezentam multiplicarea bitilor dar respectiva ambiguitate nu este jenanta); functia booleana n-ara f se va reprezenta sub forma [f] = a ⁿ a ⁿ a a . In scrierea de mai sus, 2ⁿ si 2^n reprezinta tot ridicarea la putere, dar folosim ambele notatii pentru a nu supraetaja rindul.

Matricea logica a functiei [f] de mai sus, avind la baza structura de variabile invocata, va fi reprezentata pe (n+1) linii si 2ⁿ coloane, si anume (tabelul 1)

iⁿ₀]  I 1*2^n-1*0*2^n-1

[iⁿ₁] I (1*2^n-2*0*2^n-2)*2

(M_n)  .

[iⁿ_n-1] I (1*0)*2^n-1

----- ----- --------- ----- -----

[f] I a ⁿ a ⁿ a a

Tabelul 1: reprezentarea unei functii booleene n-are

Tabelul de mai sus are in dreapta semnului 'I', pe fiecare linie, 2ⁿ biti, aliniati pe coloane bit la bit. Reprezentarea [f] va fi desemnata mai jos sub denumirea de reprezentare logica binara a functiei f. De exemplu, functia cu trei variabile f(x₀, x₁, x₂) = (x₀ x₁) x₂ = 10101000 (x₀, x₁, x₂) va avea reprezentarea din tabelul 2:

x₀ I 11110000

x₁ I 11001100

x₂ I 10101010

----- ----- --------

f I 10101000

Tabelul 2: reprezentarea functiei de trei variabile f(x₀, x₁, x₂) = 10101000(x₀, x₁, x₂)

Definitie. Spunem ca functia f I FBⁿ, cu n > 0, are variabila redundanta x_i atunci cind este constanta in componenta x_i, si anume: pentru orice sistem de valori (x₀, , x_i-1, x_i+1, , x_n-1) I B^n-1, are loc relatia:

f(x₀, , x_i-1, 1, x_i+1, , x_n-1) = f(x₀, , x_i-1, 0, x_i+1, , x_n-1).

In caz contrar, componenta x_i se numeste variabila efectiva, situatie in care exista un sistem de valori (x₀, , x_i-1, x_i+1, , x_n-1) I B^n-1, pentru care

f(x₀, , x_i-1, 1, x_i+1, , x_n-1) f(x₀, , x_i-1, 0, x_i+1, , x_n-1).

Considerind variabila redundanta x_i, cu i I [0,n-1], din matricea logica M_n vom construi o noua matrice, M_n,i, bifind din M_n toate liniile de forma (x₀, , x_i-1, 1, x_i+1, , x_n-1) acelasi rezultat l-am obtine daca am bifa toate liniile de forma (x₀, , x_i-1, 0, x_i+1, , x_n-1), datorita relatiei (1)). Vom obtine atunci 2ⁱ blocuri, fiecare in lungime de 2^(n-i-1) biti, deci noua functie, pe care o vom nota prin f₁(x₀, , x_i-1, x_i+1, x_n-1), face parte din clasa FB^n-1 iar reprezentarea ei [f₁] are o lungime de 2^n-1 biti. Din aceasta functie a disparut partea redundanta, fara valoare informationala, a functiei f.

Reciproc, functiei f₁(x₀, , x_i-1, x_i+1, , x_n-1) i se poate 'dubla' reprezentarea, prin adaugarea variabilei redundante x_i. Pentru aceasta, vom imparti reprezentarea f₁(x₀, , x_i-1, x_i+1, , x_n-1) in 2ⁱ blocuri, fiecare de lungime 2^(n-1-i); pentru obtinerea reprezentarii lui f(x₀, , x_i-1, x_i, x_i+1, , x_n-1), vom insera, dupa fiecare bloc de 2^(n-1-i) biti, acelasi bloc de biti.

Definitie. Spunem ca functia f₁, construita prin procedeul de mai sus, a fost obtinuta din f I FBⁿ prin substractia variabilei redundante x_i; reciproc, ca f este obtinuta din f prin adjunctia variabilei redundante x_i (efectiva pentru f₁, redundanta pentru f). Functia f₁ se numeste substracta lui f in clasa FBⁿ iar f, adjuncta lui f in clasa FBⁿ, notindu-se:

f₁ = Sub(fⁿ, x_i); f = Adj(f₁^n-1, x_i).

Observatie. Obtinerea functiei f₁ prin substractia variabilei x_i din functia n-ara fⁿ poate fi descrisa, conform relatarii de mai sus, si in urmatoarea notatie. [fⁿ] va desemna reprezentarea booleana a functiei n-are, in lungime de 2ⁿ biti iar [fⁿ]/2ⁱ, impartirea reprezentarii binare in 2ⁱ blocuri. Apoi fiecare dintre partile rezultate se imparte in doua jumatati, retinindu-se doar prima dintre ele, ceea ce vom nota prin '//': ([fⁿ]/2ⁱ)//2. Operatiile de mai sus se aplica fiecaruia dintre cele 2ⁱ blocuri, deci, in final:

f₁ = Sub(fⁿ, i) = (([fⁿ]/2ⁱ)//2)*2ⁱ;

cu notatii asemanatoare vom avea:

f = Adj(f^n-1, i) = (([f^n-1]/2ⁱ)**2)*2ⁱ,

unde prin '(x)**2' am notat 'dublarea' secventei 'x' (reluarea acesteia). Atit adjunctia, cit si substractia, presupun lucrul cu 2ⁱ blocuri ale variabilei x_i substractia pe blocuri de lungime 2^(n-1-p) iar adjunctia, pe blocuri de lungime 2^(n-2-p). Formulele (2) si (3) se pot aplica de indata ce am stabilit statutul variabilei x_i redundanta sau efectiva (neredundanta). Se enunta in continuare testul de redundanta in raport cu variabila x_i:

Lema 1.1 (testul de redundanta). Fie reprezentarea logica [f] a functiei booleene n-are f si variabila x_i, unde i I [0,n-1]. Urmatorul algoritm raspunde totdeauna prin 'da' sau 'nu' intrebarii: variabila x_i este redundanta?

1) Stabilim numarul secventelor de parcurs, de forma [f / 2ⁱ. Initializam procesul verificarii secventelor cu prima secventa din stinga;

2) Impartim secventa in doua, obtinind ([f] / 2ⁱ)//2;

3) Cele doua secvente rezultate din impartire coincid? Daca da, treci la 5);

4) Daca nu, afiseaza: 'variabila x_i, efectiva pentru functia f'. Treci la 7);

5) S-au incheiat secventele de examinat? Daca da, afiseaza: 'variabila x_i, redundanta pentru functia f'. Treci la 7);

6) Daca nu, ia in considerare urmatoarea secventa si treci la 2);

7) Stop.

Schita de demonstratie. Algoritmul este o prezentare sistematica a consideratiilor de mai sus din jurul definitiei variabilei redundante si a substractiei acesteia, in urma careia o functie din clasa FBⁿ se transforma intr-o functie din clasa FB^n-1 (n > 1). Algoritmul nu efectueaza substractia efectiva a variabilei x_i, ci da doar indicatii daca aceasta este posibila (in caz de variabila redundata) sau nu (neredundanta).

Observatie. Daca variabila x_i este efectiva in functia f nu se poate face nici un fel de substractie, pentru ca s-ar produce o 'pierdere de informatie' (sub forma de biti) la 'injumatatirea' functiei f. Intr-adevar, bifind liniile de forma (x₀, , x_i-1, 0, x_i+1, , x_n-1), obtinem prin substractie o noua functie, f₀(x₀, , x_i-1, 0, x_i+1, , x_n-1), diferita de f₁(x₀, , x_i-1, x_i+1, , x_n-1), deci nu putem 'condensa' reprezentarea logica [f] de la o lungime de 2^2ⁿ la una de lungime 2^2^n-1. Rezulta din aceste consideratii ca daca functia booleana n-ara are toate variabilele efective, atunci reprezentarea ei este neredundanta. (Cu alte cuvinte, nu se poate 'injumatati'.)

Exemplu. Pentru n = 5, si p = 2 functia de baza careia ii vom aplica testul de redundanta este [i⁵₂] = (1*4*0*4) * 2² = 11110000111100001111000011110000;

la intrebarea 'variabila x₀ este redundanta?', testul de redundanta da raspunsul 'da'; prin substractia variabilei x₀ ('injumatatirea' reprezentarii), obtinem [i⁵₂]⁰ = 1111000011110000;

intrebind 'variabila x₁ este redundanta?', obtinem 'da' iar prin substractie ajungem la [i⁵₂]¹ = 11001100; intrebind 'variabila x₂ este redundanta?', obtinem 'nu'; trecem la variabila x₃, pentru care obtinem 'da' si substracta [i⁵₂]² = 1010; in sfirsit, si x₄ este redundanta, ultima substractie conducind la functia unara cu reprezentarea '1*0'.

Reproducem in prealabil si o definitie dintr-o lucrare destul de cunoscuta (Yablonski, 1983):

Definitie. Doua functii booleene f si g se numesc egale (ceea ce vom nota f s g) daca se deduc una din alta prin adjunctia sau substractia unei variabile redundante.

Vom enunta in continuare o lema prin care se precizeaza numarul de functii cu variabile redundante precizate:

Lema 1.2. i) Numarul functiilor booleene n-are (n > 0) care au j variabile redundante precizate, notat FB^n,,j(i₁,, i_j), cu 1 j n, este 2^2^(n-j). ii) Numarul functiilor booleene n-are (n > 0) care au j variabile efective precizate, FB^n;;j,(i₁,, i_j), cu 1 j n, este 2^2ⁿ - 2^2^(n-j).

Demonstratie. i) Intr-adevar, numarul cerut este egal cu numarul functiilor booleene de forma f: B^n-j B, adica 2^2^(n-j), deoarece functiile respective sint constante in cele j variabile precizate si deci pot fi identificate cu functiile booleene de (n-j) variabile. ii) Pentru cea de-a doua evaluare, observam ca

FB^n;;j(i₁, , i_j) = FB^n,,n-j ([n] ),

unde prin [n] am notat multimea tuturor indicilor variabilelor incepind de la 0, si anume . Multimea din stinga si cea din dreapta, reunite, au 2^2ⁿ functii, de unde rezulta evaluarea scontata.

Teorema 1.3. Numarul functiilor booleene din FBⁿ (n > 0) cu 0 variabile redundante este

|FB^n,0 | = S _{i n} (-1)ⁱ C_nⁱ *2^2ⁱ,

notatia '|.|' reprezentind cardinalul clasei de functii.

Pentru demonstratie, se aplica lema 3 si formula lui Sylvester, rezultata din principiul incluziunii si al excluziunii (Tomescu, 1972; Ceausu, 2001).

O metoda empirica pentru determinarea de mai sus se afla si in citeva lucrari asupra functiilor booleene, cum ar fi (Carvallo,1966), insa nu este insotita de o discutie in jurul comportamentului variabilelor efective.

Exercitiu. f^2,0 = 16 - 2.4 + 2 = 10, dar si f^{2 ,1} = 4 - 2 = 4, f^2,2 = 2. Pentru clasa FB³, vom avea f^3,0 = 256 - 3.16 + 3.4 - 2 = 218, dar si f^3,1 = 2.16 - 2 = 3. 10 = 30; f^3,2 = 8 - 2 = 2.3 = 6, f^3,3 = 2.

Vom trece la descrierea notiunii de prag al unei functii booleene. Functia booleeana cu va avea o reprezentare binara compusa din 2ⁿ biti (1-pozitii sau 0-pozitii) [f] = a ⁿ a ⁿ a a

O astfel de reprezentare poate servi intr-un mod generalizat la scrierea functiei in stil infix, nu prefix, mai ales cind numarul variabilelor nu este prea mare. De exemplu, in clasa FB³ avem reprezentarea

x y z = 11111110(x, y, z),

dar putem preciza reprezentarile tuturor celorlalte functii din clasa, cu siruri de biti cuprinse intre 00000000 si 11111111. O astfel de scriere este folosita de noi in lucrarile precedente (Ceausu, 1998; Ceausu, 2000).si aplicata calculului booleean si trivalent.

Definitie. Pragul functiei f, pr(f) este numarul de 1-pozitii din reprezentarea binara cind numarul total al acestora este cel mult 2^n-1 si numarul de 0-pozitii in caz contrar. Pentru contradictie si tautologie, se ia prin conventie pragul 0.

Prin cu se noteaza multimea functiilor de prag i. Se observa ca, pentru

|FBⁿ_i| = 2. C_2^nⁱ iar |FBⁿ_2^(n-1)| = C_2^n^{2^(n-1)}.

Definitie. Functia pragul se numeste pe prag pozitiv daca 1-pozitiile nu sint preponderente in reprezentare si de prag negativ daca 0-pozitiile nu sint preponderente. Pentru pragul i=2^n-1 nu avem decit un singur tip de functii, pe care le putem denota dupa caz (neutre, pozitive sau negative).

Prin se noteaza multimea functiilor booleene n-are cu pragul pozitiv i si cu similar pentru pragul negativ i. Pragul se numeste pozitiv cind rezulta din numararea 1-pozitiilor si negativ cind rezulta din numararea 0-pozitiilor. De exemplu, in clasa FB², fiind date functiile

x y = 1110(x, y), x y = 1000(x, y),

prima are pragul negativ 1 (obtinut prin numararea 0-pozitiilor) iar cea de-a doua, pragul pozitiv 1 (obtinut prin numararea 1-pozitiilor).

Evident

Pragurile sint interesate in cadrul datorita citorva proprietati de conservare. Intr-o clasa de un anumit prag o functie este prezenta impreuna cu oglindita, negata si duala ei.

2. Ierarhizarea tablourilor automatelor celulare unidimensionale in clase de complexitate

Fie M o memorie de registre nemarginita in ambele sensuri, M = . Printr-o stare a acestei memorii vom intelege orice sir de biti s = astfel incit in aproape toate registrele sa se afle ori numarul 0, ori numarul 1. Pentru un automat celular unidimensional (ACU) starea initiala este, de regula

s₀ = .

Mai mult decit atit, definitia starii initiale a unei memorii de automat celular difera de cea a unei memorii de masina Turing, de algoritm RAM, de R-algoritm sau de orice alt algoritm clasic dintre zecile de tipuri de algoritmi prin care se realizeaza notiunea clasica de calculabilitate. O perspectiva asupra acestei probleme se gaseste in studiul (Ceausu, 1998), inspirata mai ales de lucririle (Weihrauch, 1990?) si (Cazacu, 1996). Spre deosebire de memoria starea a unui automat celular, starea initiala a unei masini Turing, a unui algoritm RAM sau a unui R-algoritm presupune ca in aproape toate registrele sa se afle numarul 0.

In cazul memoriei unui ACU, daca notam prin r_{i, j} continutul registrului i in pasul j, cu i numar intreg si j, numar natural, vom avea

s₁

s₂

si asa mai departe; pentru indicele m al unui pas suficient de mare, vom avea:

s_m

Vom folosi, in continuare, cunostinte legate de masinile Turing universale ajungind pina la constructia masinilor Turing structurate (Rdding, 1969; Brger, 1989) si de R-algoritmii universali si ierarhiile constituite in cadrul acestora (Ceausu, Cazacu, ) pentru constructia unei ierarhii de complexitate a AC unidimensionale. Pentru o masina Turing cu patru instructiuni standard ; cu un numar finit de stari dintr-o multime infinita Q = , lucrind pe o banda infinita care contine oricare din numerele 0, 1,

s =

pornind de la o stare initiala in care numarul 0 se afla in aproape toate celulele memoriei; avind citeva instructiuni standard (citirea continutului registrului vizat; scrierea unui bit in registrul vizat; deplasarea, pentru vizare, cu un registru spre stinga sau spre dreapta), functia calculata de respectiva masina se obtine astfel. Se noteaza prin C o configuratie, adica o parte activa a benzii (afectata de transformarile din pas in pas) iar trecerea la configuratia urmatoare intr-un pas al masinii se descrie prin C |-_T C₁. Activitatea masinii consta din realizarea unui proces de calcul alcatuit dintr-o succesiune de pasi cu urma din urmatoarele forme posibile:

a) C |-_T C₁ |-_T C₂ |-_T |-_T C_n (aceasta din urma fiind o configuratie finala, adica fara reprezentare in memoria interna Q);

b) C |-_T C₁ |-_T C₂ (ne-atingindu-se niciodata o configuratie finala).

Oricarei masini Turing T i se asociaza o functie T', cu T': C C

in modul urmator: fie C I C; daca procesul de calcul este de forma a), atunci T' (C) = C_n iar daca este de forma b), functia T' este nedefinita. Notam , ca mai sus, 1*x, sirul 111 in care 1 se repeta de x ori. Pentru x = 0, sirul va avea si semnificatia semnului vid, Λ. Spunem ca masina Turing T calculeaza functia aritmetica n-ara f (unde f: Nⁿ N), daca, pentru orice numere x₁, x₂, , x_n,

T'(q₁01*x₁01*x₂001*x_n) = q₀01*f (x₁, x₂, , x_n).

Pentru masina Turing de mai sus, starea interna q₀ a fost luata in considerare ca stare finala.

Pentru a determina toate functiile posibile calculate de un AC unidimensional, este suficient sa luam in discutie o celula aflata in memoria interna, r_-1, si o banda de memorie marginita la dreapta, alcatuita din registrele r₀, r₁,. Deci putem scrie

s =

notind prin indexare continutul memoriei din pas in pas.

Continutul acestei memorii in starea initiala este

s₀ =

vom scrie, comprimat, s₀ = 0/10 (punctele semnificind repetarea valorii ultimului registru). Pentru un automat celular oarecare, sa zicem cel cu regula 30 (00011110), primele patru stari au configuratiile urmatoare (nu am marcat celulele 0 din coada):

s₀ = 0/1, s₁ = 1/11, s₂ = 1/001, s₃ = 1/1111, s₄ = 1/00001,

sau, prescurtat,

0/1 |-₃₀ 1/11 |-₃₀ 1/001 |-₃₀ 1/1111 |-₃₀ 1/00001 |

(daca automatul celular este subinteles, el nu mai figureaza ca indice).

La o astfel de definire a starii memoriei unui automat celular trebuie sa ne punem problema: ce se intimpla cu partea memoriei marginita la dreapta, si anume

s' =

Pentru aceasta, dat fiind un AC cu regula f, trebuie sa construim conversul acestuia, cu regula g. Mai intii vom descre regulile unui AC.

Fie in continuare AC³ clasa automatelor celulare unidimensionale in sensul definit de Stephen Wolfram (Wolfram, 1984) si studiata la nivelul proprietatilor in toate lucrarile urmatoare, culminind cu monumentala A New Kind of Science (Wolfram, 2002). Am introdus indicele 3 luind in considerare faptul ca starea unei celule a memoriei in momentul t depinde de trei variabile: starea aceleiasi celule si a vecinilor ei din dreapta si din stinga in momentul t.

Vom defini in continuare un AC simplist la dreapta (sau la stinga), dar mai intii vom descrie regula booleeana a unui AC si subregulile componente. Un automat celular din clasa AC³ este complet caracterizat de regula sau f care, de fapt, este o functie booleana de trei variabile (f I FB³). De exemplu, automatul celular cu regula 30, f = 00011110, poate fi scris sub forma: . Grafic, valoarea 1 corespunde unei celule negre iar 0, unei celule albe.

Forma generala a unei reguli este, de fapt:

f = a a a a a a a a (x, y, z),

unde y este celula din centru si x, z celulele vecine din stinga, respectiv din dreapta, care se considera ca variabile cu valorile x = 11110000, y = 11001100, z = 10101010.

Valoarea componentelor a a indica cele opt subreguli componente ale automatului. Deci subregulile sint valuari de forma f(x, y, z) = a_i , cu i I . De exemplu, regula 30, explicit f = 00011110, se descompune in subregulile

f (1,0,0) = 1, f (0,1,1) = 1, f (0,1,0) = 1, f (0,0,1) = 1,

celelalte subreguli avind valoarea 0: Prescurtat, vom spune ca regula contine subregulile 4, 3, 2, 1 si subregulile 7', 6', 5', 0' (in dreptul celor cu valoare nula am adaugat un semn suplimentar). Subregulile cu valoarea 1 se vor numi si negre, iar subregulile cu valoarea 0 s evor numi si albe.'

Definitie. Dat fiind AC cu regula f = a a a a a a a a , automatul celular convers al acestuia va fi cel cu regula

g a a a a a a a a

deci automatul celular in care am inversat a cu a si a cu a

AC in care a a si a a se numeste autoconvers.

Observatie. Se observa ca, pentru un automat autoconvers, partea memoriei nelimitata la dreapta (si marginita la stinga de registrul r_-1 ) si partea memoriei nelimitata la stinga (si marginita la stinga de registrul r₁) au acelasi continut. Pentru o stare j oarecare si pentru continutul unui registru i in acea stare, avem:

r_{i, j} = r-_{i, j} daca i

r_{i, j} = r-_{i, j} daca i = 0.

Aceasta, deoarece a a si a a₁ inseamna, in scriere binara, a a , respectiv a a . In trecerea de la starea 0 la starea 1, celulele adaugate configuratiei la stinga si la dreapta vor fi identice, deoarece, in afara de regulile a a a si a vom mai avea regulile a a a si a , care se dezvolta la fel si la stinga, si la dreapta registrului 0.

Iata citeva automate autoconverse: Numarul acestora este destul de mare, si anume 2⁴.4 = 64. Deci un sfert dintre AC unidimensionale sint automate autoconverse.

Lema 0. Continutul memoriei marginite la dreapta al unui automat convers, memorie notata prin

s' =

este acelasi cu continutul memoriei marginite la stinga a automatului celular convers, si anume

s =

Rezultatul de mai sus ne permite sa lucram sistematic numai cu stari ale memoriei de tipul celor de mai sus memorie marginita la stinga, nemarginita la dreapta si dispunind de celula r_-1, care serveste ca memorie interna

Definitie. Vom numi in continuare un tablou T al unui automat celular un istoric al tuturor starilor, ceea ce presupune luarea in considerare a multimii

T =

Intre toate subregulile, cele cu f(0, 0, 0) sau f(1, 1, 1) in partea dreapta au un rol special, datorita starii initiale a memoriei si a starilor ei ulterioare, in care doar aceste subreguli se pot aplica, eventual, de o infinitate de ori. Dupa aceste stari, vom opera urmatoarea partitie in rindul automatelor celulare:

A) automate celulare cu tablou alb, in care aproape toate registrele, din pas in pas, sint albe; acestea contin subregula 0';

N) automate celulare cu tablou negru, in care aproape toate registrele, din pas in pas, sint albe; acestea contin subregulile 0 si 7;

M) automate celulare cu tablou mixt, in care aproape toate registrele, din pas in pas, sint fie albe, fie negre; acestea contin subregulile 0 si 7'.

Notind ACA multimea automatelor celulare cu tablou alb si ACN si ACM celelalte clase de automate celulare, vom avea, evident:

AC = ACA ACN ACM

cele trei clase fiind si disjuncte. In total, din cele 256 AC unidimensionale, o jumatate vor avea tablou alb, un sfert, tablou negru si un alt sfert, tablou mixt.

Ca exemplu, automatul 30 (00011110) este cu tablou alb (a cu tablou mixt (deoarece a a ) iar 159 (100011110), cu tablou negru (deoarece a a

Demonstratie. Automatele cu regulile 1111, 0000, 1100, 0011, 1010, 0101 sint sugur simpliste, deoarece nu depind decit de cel mult o variabila. De exemplu, pentru f = 0101 pornind de la starea s₀ = 010, vom avea s₁ =

Ne vom referi in continuare la o binecunoscuta ierarhie in patru clase a automatelor celulare, stabilita din lucrarile lui Stephen Wolfram (Wolfram, 1983), cu precizari ulterioare stabilite de John L. Casti (Casti, 2000)

AC₁ : the initial pattern dissapears (evolution leads to a homogeneous state);

AC₂ : the initial pattern evolves to a fixed finite size (a set of stable or periodic structures that are separeatd and simple);

AC₃ : the initial pattern grows indefinitely at a fixed rate;

AC₄: the initial pattern grows and contracts with time.

John L. Casti incearca o comparatie inversa a acestei ierarhii cu cele patru clase de limbaje formale ale ierarhiei limbajelor formale ale lui Chomsky (Cast, 2000, p. 194): class AC₁ and AC₂ of cellular automata have limit sets that form regular languages and class AC₄ seems to correspond to general unrestricted languages. Insa, fata de o MT, care nu schimba toata configuratia unei stari a memoriei, ci doar o celula vizata (aproape toate celulele memoriei avind valoarea 0), pentru un automat celular toate celulele memoriei sint, practic, celule vizate cu alte cuvinte, asa cum arata si lucrarile lui Stephen Wolfram, un AC unidimensional este mai complex decit o masina Turing: O MT este, practic, un AC unidimensional cu o singura celula vizata la un moment dat. Ne putem astepta, deci, ca AC unidimensionale sa genereze ierarhii mai complexe decit masinile Turing. Ceea ce inseamna ca ele vor alcatui o ierarhie mai sofisticata decit masinile Turing.

Un prim rezultat stabileste o legatura intre eventualele variabile fictive ale regulei unui AC si clasa de complexitate a acestuia:

Teorema 1. i) Daca regula unui AC are cel putin o variabila fictiva, el este de clasa AC₀ sau AC₁. ii) Toate AC de clasa AC₂ sau AC₃ au in regula numai variabile efective.

Demonstratie. Se inspecteaza semitablourile drepte ale celor 256 de AC unidimensionale listate pina la s₁₅, dar asta are o mai mica importanta. Se localizeaza AC cu reguli

i) care au trei variabile fictive (11111111, 0000);

ii) care au doua variabile fictive (11110000,11001100, 10101010 si negatiile lor);

iii) care au o singura variabila fictiva; intre ele, sint 10 AC in care variabila fictiva este x (11101110, 11011101, 10111011, 1001. 0111 si negatiile acestora), alte 10 in care variabila fictiva este z.

Se observa ca toate AC cu regulile avind forma de mai sus sint de clasa de clasa AC₀ sau AC₁. Rezultatul de la punctul ii) este o consecnta directa a celui de la punctul i).

Observatie. Se observa ca teorema 1 se aplica unui numar de 38 de AC unidimensionale.

In prealabil, vom considera un AC simplificat alcatuit dintr-o celula si din succesoarea acesteia si cu o regula de forma f I FB², f = a a a a (x, y), unde x este celula de baza si y, succesoarea acesteia. Multimea tuturor acestor automate celulare unidimensionale o vom nota prin AC² datorita celor doi parametri a i functiei booleene care reprezinta regula. Pornind de la starea s₀ = 010, vom avea in continuare starile

s₁ = a a a a a a a

s₂ = a a a a a a a a a a a a

In descrierea starii s₂, notatia a a a ar trebui citita astfel a cu indicii a si a si am adptat-o pentru a nu supra-etaja notatia indicilor. Nu este greu de demonstrat rezultatul, in perfecta consonanta cu teorema 1:

Lema 2. Toate cele 16 automate din clasa AC² sint de clasa AC₁ si AC₂.

Un alt rezultat stabileste o legatura interesanta intre pragul functiei care reprezinta regula si clasa de complexitate a respectivului AC unidimensional:

Teorema 3. i) Daca pragul functiei booleene care reprezinta regula este 0, 1 sau 2, atunci AC respectiv este de clasa AC₁ si AC₂. Exista doar cu trei exceptii de la aceasta regula: doua AC cu semi-tablou alb, si anume 16 (00010010) si unul cu semi-tablou negru, si anume 225. ii) Toate AC de clasa AC₂ sau AC₃ au ca regula o functie booleeana de prag 3 sau 4. Demonstratie. Se inspecteaza semitablourile drepte ale celor 256 de AC unidimensionale (listate pina la s₁₅, dar asta are o mai mica importanta). Se localizeaza AC cu reguli reprezentate prin functii

i) de prag 0 (11111111, 0000);

ii) de prag 1 (10000000,01000000,, 00000001 si negatiile lor);

iii) de prag 2 (11000000,10100000, 10010000, , 00000011 si negatiile lor).

Se observa ca toate AC cu regulile avind forma de mai sus sint de clasa de clasa AC₀ sau AC₁, cu doar trei exceptii: automatele cu regulile 16, si 225. Rezultatul de la punctul ii) este o consecinta directa a celui de la punctul i).

Observatie. Se observa ca teorema 1 se aplica unui numar de 60 de AC unidimensionale (2 , din care se scad 3 exceptii, deci ramin 57 de cazuri.

Legind teoremele 1 si 2, obtinem o interesanta caracterizare a AC din clasele AC₃ sau AC₄:

Teorema 4. AC unidimensional apartine claselor de cmplexitate AC₃ sau AC₄ si numai daca regula care il reprezinta:

i) este o functie de prag 3 sau 4;

ii) nu are variabile fictive;

iii) nu simuleaza activitatea unui AC cu regula de prag mai mic decit 3.

Un al doilea rezultat (care se aplica unui numar de 60 de automate celulare unidimensionale) stabileste faptul ca daca pragul functiei booleene care reprezinta regula este 0, 1 sau 2, atunci AC respectiv este de clasa AC₁ si AC₂ (doar cu sase exceptii de AC liniare). Rezulta imediat ca toate AC de clasa AC₃ sau AC₄ au ca regula o functie booleeana de prag 3 sau 4.

Note

Alagič, Suad; Arbib, Michael A., The Design of Well Structured and Correct Programs, Springer-Verlag, New York, 1978

Brger, Egon, Computability, Complexity, Logic, North Holland, Amsterdam, 1989, pp. 20-27

Cazacu, C., 1996, Teoria calculabilitatii efective, Editura Universitatii Al. I. Cuza, Iasi, cap. al IV-lea si al V-lea

Casti, John L., Reality Rules: I. Picturing the World in Mathematics The Fundamentals, John Willey and Sons, New York, 2000, pp. 161-249

Ceausu, George, Teoremele de incompletitudine ale lui Gdel semnificatii logice si aplicatii extralogice (teza de doctorat), Universitatea 'Al. I. Cuza', Iasi, 1998, cap. al III-lea

Cox, David A, 1996, Introduction to Fermat's Last Theorem, The American Mathematical Monthly / Jan. 1996, pp. 3-14

Dalen, Dirk van, 1986, Intuitionistic Logic, in: Gabbay, D.; Guenthner, F. (ed.) Handbook of Philosophical Logic, vol. al III-lea, D. Reidel Publ. Comp, Amsterdam, pp. 225-339

Garey, M. R., Johnson, D. S., 1979, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, San Francisco, 215 sqq.

Jones, J. P.; Matijasevič, Yu. V., 1984, Register machine proof of the theorem on exponential diophantine reprezentation of enumerable sets, The Journal of Symbolic Logic, an 49, nr. 3

Kozen, Dexter, 1992, The Design and Analysis of Algorithms, Springer-Verlag, New York, pp. 111-133

Kowalski, Robert, 1979, Logic for Problem Solving, North Holland, New York

Mandelbrot, Bennoit, 1978, Fractals: Form, Chance, and Dimension, W. H. Freeman and Comp., W. H. Freeman, San Francisco

Rdding, D., Einfhrung in die Theorie der berechenbaren Funktionen, Vorlesungscript, Institut fr mathematische Logik und Grundlagenforschung, Universitt Mnster, 1969

Safarevici, I. R., 1989, Notiunile fundamentale ale algebrei, Editura Academiei, Bucuresti, cap. I.

Wolfram, Stephen, Cellular Automata as Simple-Organizing Systems, 1982

Wolfram, Stephen, Cellular Automata, 1983

George CEAUSU

Facultatea de Filosofie

Universitatea 'Al. I. Cuza', Iasi

ceausu@uaic.ro