| dc.date.accessioned |
2012-12-18T06:40:26Z |
und |
| dc.date.accessioned |
2017-10-24T12:21:48Z |
|
| dc.date.available |
2012-12-18T06:40:26Z |
und |
| dc.date.available |
2017-10-24T12:21:48Z |
|
| dc.date.issued |
2012-12-18T06:40:26Z |
|
| dc.identifier.uri |
http://radr.hulib.helsinki.fi/handle/10138.1/2260 |
und |
| dc.identifier.uri |
http://hdl.handle.net/10138.1/2260 |
|
| dc.title |
Reversibilitetsproblemet för tvådimensionella cellulära automater |
sv |
| ethesis.discipline |
Mathematics |
en |
| ethesis.discipline |
Matematiikka |
fi |
| ethesis.discipline |
Matematik |
sv |
| ethesis.discipline.URI |
http://data.hulib.helsinki.fi/id/44bc4f03-6035-4697-993b-cfc4cea667eb |
|
| ethesis.department.URI |
http://data.hulib.helsinki.fi/id/61364eb4-647a-40e2-8539-11c5c0af8dc2 |
|
| ethesis.department |
Institutionen för matematik och statistik |
sv |
| ethesis.department |
Department of Mathematics and Statistics |
en |
| ethesis.department |
Matematiikan ja tilastotieteen laitos |
fi |
| ethesis.faculty |
Matematisk-naturvetenskapliga fakulteten |
sv |
| ethesis.faculty |
Matemaattis-luonnontieteellinen tiedekunta |
fi |
| ethesis.faculty |
Faculty of Science |
en |
| ethesis.faculty.URI |
http://data.hulib.helsinki.fi/id/8d59209f-6614-4edd-9744-1ebdaf1d13ca |
|
| ethesis.university.URI |
http://data.hulib.helsinki.fi/id/50ae46d8-7ba9-4821-877c-c994c78b0d97 |
|
| ethesis.university |
Helsingfors universitet |
sv |
| ethesis.university |
University of Helsinki |
en |
| ethesis.university |
Helsingin yliopisto |
fi |
| dct.creator |
Sundberg, Heidi Carina Beatrice |
|
| dct.issued |
2012 |
|
| dct.language.ISO639-2 |
swe |
|
| dct.abstract |
I den här avhandlingen behandlas cellulära automater och speciellt deras reversibilitet. Avhandlingens fokus ligger vid att bevisa att reversibilitetsproblemet är oavgörbart för tvådimensionella cellulära automater, med andra ord att det inte existerar en algoritm för att bestämma om en tvådimensionel cellulär automat är reversibel.
Avhandlingen inleds med introduktionen av grundläggande definitioner och begrepp gällande cellulära automater. I kapitel 2 undersöker vi existensen av Edens trädgård-konfigurationer hos cellulära automater. En Edens trädgård-konfiguration är en konfiguration som endast kan förekomma som startkonfiguration hos den cellulära automaten ifråga. Vi bevisar också Edens trädgård-satsen som ursprungligen presenterades av Edward F. Moore och John Myhill. Tillsammans med Curtis-Hedlund-Lyndon satsen som presenteras i kapitel 3, möjliggör Edens trädgård-satsen beviset av att en cellulär automat är reversibel om och endast om dess globala funktion är injektiv. Detta bevis presenteras i kapitel 3 och utgör en grundläggande ingredient i beviset av att reversibilitetsproblemet är oavgörbart för tvådimensionella cellulära automater.
I kapitel 4 bekantar vi oss med begrepp som krävs för att förstå vad oavgörbarhet innebär. Begrepp som behandlas är bl.a. Turingmaskin och algoritm. Kapitel 5 inleds med introduktionen av kaklingsproblemet samt diverse viktiga definitioner i anknytning till detta problem. Här presenteras och bevisas också en sats som utgör det sista grundantagandet i beviset av reversibilitetsproblemets oavgörbarhet för tvådimensionella cellulära automater. Detta bevis behandlas i avhandlingens sista kapitel. |
sv |
| dct.language |
sv |
|
| ethesis.language.URI |
http://data.hulib.helsinki.fi/id/languages/swe |
|
| ethesis.language |
Swedish |
en |
| ethesis.language |
ruotsi |
fi |
| ethesis.language |
svenska |
sv |
| ethesis.thesistype |
pro gradu-avhandlingar |
sv |
| ethesis.thesistype |
pro gradu -tutkielmat |
fi |
| ethesis.thesistype |
master's thesis |
en |
| ethesis.thesistype.URI |
http://data.hulib.helsinki.fi/id/thesistypes/mastersthesis |
|
| dct.identifier.urn |
URN:NBN:fi-fe2017112251668 |
|
| dc.type.dcmitype |
Text |
|
