Automaattiryhmien algebrallisia tuloksia ja ratkeavuusongelmia
Hotanen, Toni (2017-11-13)
Automaattiryhmien algebrallisia tuloksia ja ratkeavuusongelmia
(13.11.2017)
Turun yliopisto
avoin
Julkaisun pysyvä osoite on:
https://urn.fi/URN:NBN:fi-fe2017111350649
https://urn.fi/URN:NBN:fi-fe2017111350649
Tiivistelmä
Tässä teoksessa esitetään kaksi ryhmäteoriaa koskevaa ongelmaa ja niiden ratkaisu käyttäen hyväksi erästä automaattiryhmää, joka tunnetaan nimellä Grigorchukin ryhmä. Nähdään, että kyseinen ryhmä on ääretön 2-ryhmä ja sillä on keskitason kasvu.
Lisäksi esitetään automaattiryhmiä ja -puoliryhmiä koskevia päätösongelmia. Nähdään, että sanaongelma on automaattipuoliryhmien joukossa ratkeava, kun taas muut teoksessa esitetyt päätösongelmat ovat ratkeamattomia.
Johdannon jälkeen ensimmäisessä luvussa käydään läpi esitystä seuraamiseen tarvittavat ryhmäteorian tiedot. Kolmannessa luvussa esitetään automaattiryhmien ja -puoliryhmien määritelmät ja muutamia tuloksia.
Neljännessä luvussa esitetään Grigorchukin ryhmä ja sen avulla ratkaisut sekä Burnsiden ongelmaan että Milnorin ongelmaan.
Viimeisessä luvussa esitetään automaattiryhmiä ja -puoliryhmiä koskevia päätösongelmia.
Lisäksi esitetään automaattiryhmiä ja -puoliryhmiä koskevia päätösongelmia. Nähdään, että sanaongelma on automaattipuoliryhmien joukossa ratkeava, kun taas muut teoksessa esitetyt päätösongelmat ovat ratkeamattomia.
Johdannon jälkeen ensimmäisessä luvussa käydään läpi esitystä seuraamiseen tarvittavat ryhmäteorian tiedot. Kolmannessa luvussa esitetään automaattiryhmien ja -puoliryhmien määritelmät ja muutamia tuloksia.
Neljännessä luvussa esitetään Grigorchukin ryhmä ja sen avulla ratkaisut sekä Burnsiden ongelmaan että Milnorin ongelmaan.
Viimeisessä luvussa esitetään automaattiryhmiä ja -puoliryhmiä koskevia päätösongelmia.