Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE




loading...



BulgaraCeha slovacaCroataEnglezaEstonaFinlandezaFranceza
GermanaItalianaLetonaLituanianaMaghiaraOlandezaPoloneza
SarbaSlovenaSpaniolaSuedezaTurcaUcraineana

AdministrationAnimalsArtBiologyBooksBotanicsBusinessCars
ChemistryComputersComunicationsConstructionEcologyEconomyEducationElectronics
EngineeringEntertainmentFinancialFishingGamesGeographyGrammarHealth
HistoryHuman-resourcesLegislationLiteratureManagementsManualsMarketingMathematic
MedicinesMovieMusicNutritionPersonalitiesPhysicPoliticalPsychology
RecipesSociologySoftwareSportsTechnicalTourismVarious

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

Mathematic

+ Font mai mare | - Font mai mic








DOCUMENTE SIMILARE

Trimite pe Messenger
LF axis of true position dimension of a square
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 FBn 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,2n-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 AC1 si AC2, pe de o parte, si AC3 si AC4 , 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 AC1 sau AC2. Rezulta, deci, ca toate AC de clasa AC3 sau AC4 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 AC0 si AC1 (doar cu trei exceptii de AC, exceptii bine motivate). Rezulta imediat ca toate AC de clasa AC2 sau AC3 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 CA1 si CA2, on the one hand, and CA3 si CA4, 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 CA1 or CA2 classes. It result that all CA of CA3 or CA4 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 AC1 or AC2 classes (excepting three CA, good motivated exceptions). It result directly that all CA of CA3 or CA4 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, inp, 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 'x1', de exemplu, vom fi in posesia unei reprezentari vagi, caci reprezentarea [x1] se poate intinde pe orice lungime de tip 2n, 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 FBn 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 xp prin (inp),

(inp) = ((1*2^(n-p-1))(0*2^(n-p-1))*2p

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 n a n a a . In scrierea de mai sus, “2n” 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 2n coloane, si anume (tabelul 1)

in0]  I 1*2n-1*0*2n-1

[in1] I (1*2n-2*0*2n-2)*2

(Mn)  .

[inn-1] I (1*0)*2n-1

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

[f] I a n a n a a

Tabelul 1: reprezentarea unei functii booleene n-are

Tabelul de mai sus are in dreapta semnului 'I', pe fiecare linie, 2n 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(x0, x1, x2) = (x0 x1) x2 = 10101000 (x0, x1, x2) va avea reprezentarea din tabelul 2:

x0 I 11110000

x1 I 11001100

x2 I 10101010

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

f I 10101000

Tabelul 2: reprezentarea functiei de trei variabile f(x0, x1, x2) = 10101000(x0, x1, x2)

Definitie. Spunem ca functia f I FBn, cu n > 0, are variabila redundanta xi atunci cind este constanta in componenta xi, si anume: pentru orice sistem de valori (x0, , xi-1, xi+1, , xn-1) I Bn-1, are loc relatia:

f(x0, , xi-1, 1, xi+1, , xn-1) = f(x0, , xi-1, 0, xi+1, , xn-1).

In caz contrar, componenta xi se numeste variabila efectiva, situatie in care exista un sistem de valori (x0, , xi-1, xi+1, , xn-1) I Bn-1, pentru care

f(x0, , xi-1, 1, xi+1, , xn-1) f(x0, , xi-1, 0, xi+1, , xn-1).

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

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

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

f1 = Sub(fn, xi); f = Adj(f1n-1, xi).

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

f1 = Sub(fn, i) = (([fn]/2i)//2)*2i;

cu notatii asemanatoare vom avea:

f = Adj(fn-1, i) = (([fn-1]/2i)**2)*2i,

unde prin '(x)**2' am notat 'dublarea' secventei 'x' (reluarea acesteia). Atit adjunctia, cit si substractia, presupun lucrul cu 2i blocuri ale variabilei xi – 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 xi – redundanta sau efectiva (neredundanta). Se enunta in continuare testul de redundanta in raport cu variabila xi:

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

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

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

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

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

5) S-au incheiat secventele de examinat? Daca da, afiseaza: 'variabila xi, 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 FBn se transforma intr-o functie din clasa FBn-1 (n > 1). Algoritmul nu efectueaza substractia efectiva a variabilei xi, ci da doar indicatii daca aceasta este posibila (in caz de variabila redundata) sau nu (neredundanta).

Observatie. Daca variabila xi 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 (x0, , xi-1, 0, xi+1, , xn-1), obtinem prin substractie o noua functie, f0(x0, , xi-1, 0, xi+1, , xn-1), diferita de f1(x0, , xi-1, xi+1, , xn-1), deci nu putem 'condensa' reprezentarea logica [f] de la o lungime de 2^2n la una de lungime 2^2n-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 [i52] = (1*4*0*4) * 22 = 11110000111100001111000011110000;

la intrebarea 'variabila x0 este redundanta?', testul de redundanta da raspunsul 'da'; prin substractia variabilei x0 ('injumatatirea' reprezentarii), obtinem [i52]0 = 1111000011110000;

intrebind 'variabila x1 este redundanta?', obtinem 'da' iar prin substractie ajungem la [i52]1 = 11001100; intrebind 'variabila x2 este redundanta?', obtinem 'nu'; trecem la variabila x3, pentru care obtinem 'da' si substracta [i52]2 = 1010; in sfirsit, si x4 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 FBn,,j(i1,, ij), cu 1 j n, este 2^2^(n-j). ii) Numarul functiilor booleene n-are (n > 0) care au j variabile efective precizate, FBn;;j,(i1,, ij), cu 1 j n, este 2^2n - 2^2^(n-j).

Demonstratie. i) Intr-adevar, numarul cerut este egal cu numarul functiilor booleene de forma f: Bn-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

FBn;;j(i1, , ij) = FBn,,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^2n functii, de unde rezulta evaluarea scontata.

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

|FBn,0 | = S i n (-1)i Cni *2^2i,

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. f2,0 = 16 - 2.4 + 2 = 10, dar si f2 ,1 = 4 - 2 = 4, f2,2 = 2. Pentru clasa FB3, vom avea f3,0 = 256 - 3.16 + 3.4 - 2 = 218, dar si f3,1 = 2.16 - 2 = 3. 10 = 30; f3,2 = 8 - 2 = 2.3 = 6, f3,3 = 2.

Vom trece la descrierea notiunii de prag al unei functii booleene. Functia booleeana cu va avea o reprezentare binara compusa din 2n biti (1-pozitii sau 0-pozitii) [f] = a n a n 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 FB3 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 2n-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

|FBni| = 2. C2^ni iar |FBn2^(n-1)| = C2^n2^(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=2n-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 FB2, 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

s0 = .

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 ri, j continutul registrului i in pasul j, cu i numar intreg si j, numar natural, vom avea

s1

s2

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

sm

Vom folosi, in continuare, cunostinte legate de masinile Turing universale ajungind pina la constructia masinilor Turing structurate (Rödding, 1969; Börger, 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 C1. Activitatea masinii consta din realizarea unui proces de calcul alcatuit dintr-o succesiune de pasi cu urma din urmatoarele forme posibile:

a) C |-T C1 |-T C2 |-T |-T Cn (aceasta din urma fiind o configuratie finala, adica fara reprezentare in memoria interna Q);

b) C |-T C1 |-T C2 (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) = Cn 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: Nn N), daca, pentru orice numere x1, x2, , xn,

T'(q101*x101*x2001*xn) = q001*f (x1, x2, , xn).

Pentru masina Turing de mai sus, starea interna q0 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 r0, r1,. Deci putem scrie

s =

notind prin indexare continutul memoriei din pas in pas.

Continutul acestei memorii in starea initiala este

s0 =

vom scrie, comprimat, s0 = 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):

s0 = 0/1, s1 = 1/11, s2 = 1/001, s3 = 1/1111, s4 = 1/00001,

sau, prescurtat,

0/1 |-30 1/11 |-30 1/001 |-30 1/1111 |-30 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 AC3 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 AC3 este complet caracterizat de regula sau f care, de fapt, este o functie booleana de trei variabile (f I FB3). 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) = ai , 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 r1) au acelasi continut. Pentru o stare j oarecare si pentru continutul unui registru i in acea stare, avem:

ri, j = r-i, j daca i

ri, j = r-i, j daca i = 0.

Aceasta, deoarece a a si a a1 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 24.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 s0 = 010, vom avea s1 =

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)

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

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

AC3 : the initial pattern grows indefinitely at a fixed rate;

AC4: 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 AC1 and AC2 of cellular automata have limit sets that form regular languages and class AC4 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 AC0 sau AC1. ii) Toate AC de clasa AC2 sau AC3 au in regula numai variabile efective.

Demonstratie. Se inspecteaza semitablourile drepte ale celor 256 de AC unidimensionale listate pina la s15, 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 AC0 sau AC1. 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 FB2, 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 AC2 datorita celor doi parametri a i functiei booleene care reprezinta regula. Pornind de la starea s0 = 010, vom avea in continuare starile

s1 = a a a a a a a

s2 = a a a a a a a a a a a a

In descrierea starii s2, 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 AC2 sint de clasa AC1 si AC2.

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 AC1 si AC2. 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 AC2 sau AC3 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 s15, 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 AC0 sau AC1, 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 AC3 sau AC4:

Teorema 4. AC unidimensional apartine claselor de cmplexitate AC3 sau AC4 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 AC1 si AC2 (doar cu sase exceptii de AC liniare). Rezulta imediat ca toate AC de clasa AC3 sau AC4 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

Börger, 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 Gödel 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

Rödding, D., Einführung in die Theorie der berechenbaren Funktionen, Vorlesungscript, Institut für mathematische Logik und Grundlagenforschung, Universität Münster, 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



loading...






Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 664
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2020 . All rights reserved

Distribuie URL

Adauga cod HTML in site