Epäuniformien soluautomaattien surjektiivisuus- ja injektiivisyysominaisuuksia
Paturi, Pyry (2022-10-06)
Epäuniformien soluautomaattien surjektiivisuus- ja injektiivisyysominaisuuksia
Paturi, Pyry
(06.10.2022)
Julkaisu on tekijänoikeussäännösten alainen. Teosta voi lukea ja tulostaa henkilökohtaista käyttöä varten. Käyttö kaupallisiin tarkoituksiin on kielletty.
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2022101261756
https://urn.fi/URN:NBN:fi-fe2022101261756
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.
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.