A Uniquely Ergodic Cellular Automaton

Tietueen suppeat tiedot
dc.contributor.authorIlkka Törmä
dc.contributor.organizationfi=Turun tietotekniikan tutkimuskeskus TUCS|en=Turku Centre for Computer Science (TUCS)|
dc.contributor.organizationfi=matematiikka|en=Mathematics|
dc.contributor.organization-code1.2.246.10.2458963.20.41687507875
dc.converis.publication-id3362736
dc.converis.urlhttps://research.utu.fi/converis/portal/Publication/3362736
dc.date.accessioned2022-10-28T13:36:55Z
dc.date.available2022-10-28T13:36:55Z
dc.description.abstract<p> We construct a one-dimensional uniquely ergodic cellular automaton which is not nilpotent. This automaton can perform asymptotically infinitely sparse computation, which nevertheless never disappears completely. The construction builds on the self-simulating automaton of G&aacute;cs. We also prove related results of dynamical and computational nature, including the undecidability of unique ergodicity, and the undecidability of nilpotency in uniquely ergodic cellular automata.</p>
dc.format.pagerange415
dc.format.pagerange442
dc.identifier.jour-issn0022-0000
dc.identifier.olddbid183116
dc.identifier.oldhandle10024/166210
dc.identifier.urihttps://www.utupub.fi/handle/11111/40476
dc.identifier.urnURN:NBN:fi-fe2021042715168
dc.language.isoen
dc.okm.affiliatedauthorTörmä, Ilkka
dc.okm.affiliatedauthorDataimport, Turun tietotekniikan tutkimuskeskus TUCS
dc.okm.discipline111 Mathematicsen_GB
dc.okm.discipline113 Computer and information sciencesen_GB
dc.okm.discipline111 Matematiikkafi_FI
dc.okm.discipline113 Tietojenkäsittely ja informaatiotieteetfi_FI
dc.okm.internationalcopublicationnot an international co-publication
dc.okm.internationalityInternational publication
dc.okm.typeA1 ScientificArticle
dc.publisherElsevier
dc.publisher.countryUnited Statesen_GB
dc.publisher.countryYhdysvallat (USA)fi_FI
dc.publisher.country-codeUS
dc.relation.doi10.1016/j.jcss.2014.10.001
dc.relation.ispartofjournalJournal of Computer and System Sciences
dc.relation.issue2
dc.relation.volume81
dc.source.identifierhttps://www.utupub.fi/handle/10024/166210
dc.titleA Uniquely Ergodic Cellular Automaton
dc.year.issued2015

Tiedostot

Näytetään 1 - 1 / 1
Name:
submission.pdf
Size:
646.25 KB
Format:
Adobe Portable Document Format
Description:
Author's Post-print
Lataa

Kokoelmat

Rinnakkaistallenteet