Epäuniformien soluautomaattien surjektiivisuus- ja injektiivisyysominaisuuksia
501.65 KB
avoin
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
Lataukset187
Pysyvä osoite
Verkkojulkaisu
DOI
Tiivistelmä
Tämä työ koostuu kirjallisuuskatsauksesta tavallisiin ja epäuniformeihin soluautomaatteihin, sekä rajoitetun Eedenin puutarhalauseen todistuksesta epäuniformeille soluautomaateille.
Työn ensimmäisessä osiossa tarkastellaan tavallisia soluautomaatteja. Esitetään näiden perusominaisuuksia, ja todistetaan Eedenin puutarhalause.
Seuraavassa osassa tarkastellaan epäuniformeja soluautomaatteja. Surjektiivisten sääntöjakaumien joukon osoitetaan olevan siirtoavaruus, ja injektiivisten sääntöjakaumien joukon olevan ωω-säännöllinen. Lisäksi näytetään, että Eedenin puutarhalause ei päde epäuniformeille soluautomaateille yleisesti, mutta päteen periodisten sääntöjakaumien tapauksessa.
Viimeisessä osiossa tarkastellaan epäuniformeja soluautomaatien rekurrentteja sääntöjakaumia. Erityisesti todistetaan, että Eedenin puutarhalause pätee rekurrenteille sääntöjaumille. Lisäksi esitetään vastaesimerkit ei-rekurrenteille sääntöjakaumille.