Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-07

AUTHORS

Jarkko Kari

ABSTRACT

A cellular automaton is a dynamical system on an infinite array of cells defined by a local update rule that is applied simultaneously at all cells. By carefully choosing the update rule, the global dynamics can be made information preserving. In this case, the cellular automaton is called reversible. In this article, we explain fundamental classical results concerning reversible cellular automata and discuss some more recent developments on selected topics. Classical results reviewed include the Curtis–Hedlund–Lyndon theorem, the Garden-of-Eden theorem and the invariance of uniform Bernoulli distribution under reversible cellular automata. We then describe several techniques to construct reversible cellular automata and a method to determine whether a given one-dimensional automaton is reversible. We present undecidability issues concerning reversible cellular automata and discuss three types of universality: computational universality, intrinsic universality, and physical universality. We finish with short notes about time symmetry, expansiveness, and conservation laws. More... »

PAGES

145-172

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6

DOI

http://dx.doi.org/10.1007/s00354-018-0034-6

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1105086529


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0601", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biochemistry and Cell Biology", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/06", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Biological Sciences", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "University of Turku", 
          "id": "https://www.grid.ac/institutes/grid.1374.1", 
          "name": [
            "Department of Mathematics and Statistics, University of Turku, 20014, Turku, Finland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kari", 
        "givenName": "Jarkko", 
        "id": "sg:person.011735452354.35", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011735452354.35"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "https://doi.org/10.1090/s0002-9939-1963-0155764-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000280146"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0061728", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000307890", 
          "https://doi.org/10.1007/bfb0061728"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-92910-9_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1000675121", 
          "https://doi.org/10.1007/978-3-540-92910-9_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0019-3577(93)90040-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001465095"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0304-3975(95)00038-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1002866933"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(91)90150-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004501638"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(91)90150-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004501638"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11505877_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004669217", 
          "https://doi.org/10.1007/11505877_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11505877_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1004669217", 
          "https://doi.org/10.1007/11505877_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(05)80025-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1006334600"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1038/scientificamerican1070-120", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007582166", 
          "https://doi.org/10.1038/scientificamerican1070-120"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2004.11.021", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008892501"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(90)90195-u", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010901944"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(90)90195-u", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1010901944"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01201813", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011622046", 
          "https://doi.org/10.1007/bf01201813"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01201813", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011622046", 
          "https://doi.org/10.1007/bf01201813"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2008.01.041", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012017670"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0304-3975(96)00081-3", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1012430781"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(72)80009-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1016636649"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(84)90253-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017085534"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(84)90253-7", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1017085534"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(84)90252-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024857421"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(84)90252-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1024857421"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-20712-9_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027023655", 
          "https://doi.org/10.1007/978-3-642-20712-9_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-20712-9_17", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1027023655", 
          "https://doi.org/10.1007/978-3-642-20712-9_17"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2011.02.023", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1028506815"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s11047-010-9222-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030150049", 
          "https://doi.org/10.1007/s11047-010-9222-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4471-0129-1_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030314599", 
          "https://doi.org/10.1007/978-1-4471-0129-1_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-1-4471-0129-1_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030314599", 
          "https://doi.org/10.1007/978-1-4471-0129-1_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(72)80013-8", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032327804"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-85238-4_34", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032588457", 
          "https://doi.org/10.1007/978-3-540-85238-4_34"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01857727", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032661873", 
          "https://doi.org/10.1007/bf01857727"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01857727", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032661873", 
          "https://doi.org/10.1007/bf01857727"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10955-015-1281-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032836701", 
          "https://doi.org/10.1007/s10955-015-1281-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s10955-015-1281-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1032836701", 
          "https://doi.org/10.1007/s10955-015-1281-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2011.02.024", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035046025"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11523468_34", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035438053", 
          "https://doi.org/10.1007/11523468_34"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11523468_34", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1035438053", 
          "https://doi.org/10.1007/11523468_34"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jcss.2012.01.006", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041095532"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://app.dimensions.ai/details/publication/pub.1041394511", 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-14034-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041394511", 
          "https://doi.org/10.1007/978-3-642-14034-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-14034-1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041394511", 
          "https://doi.org/10.1007/978-3-642-14034-1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.tcs.2011.12.037", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041614651"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/2688073.2688107", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044103794"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(90)90185-r", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044244052"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/0167-2789(90)90185-r", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044244052"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/s0022-0000(77)80007-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1046362897"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01691062", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049449230", 
          "https://doi.org/10.1007/bf01691062"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01691062", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049449230", 
          "https://doi.org/10.1007/bf01691062"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01691062", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1049449230", 
          "https://doi.org/10.1007/bf01691062"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.31.276", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060777564"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1103/physrevlett.31.276", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1060777564"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1142/s0129054195000202", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1062897674"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/rd.176.0525", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063180324"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-58741-7_23", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086750862", 
          "https://doi.org/10.1007/978-3-319-58741-7_23"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-58741-7_35", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1086750874", 
          "https://doi.org/10.1007/978-3-319-58741-7_35"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/psapm/014/9961", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1089193116"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/conm/469/09161", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1089202801"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1017/cbo9780511549755", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1098679392"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-07", 
    "datePublishedReg": "2018-07-01", 
    "description": "A cellular automaton is a dynamical system on an infinite array of cells defined by a local update rule that is applied simultaneously at all cells. By carefully choosing the update rule, the global dynamics can be made information preserving. In this case, the cellular automaton is called reversible. In this article, we explain fundamental classical results concerning reversible cellular automata and discuss some more recent developments on selected topics. Classical results reviewed include the Curtis\u2013Hedlund\u2013Lyndon theorem, the Garden-of-Eden theorem and the invariance of uniform Bernoulli distribution under reversible cellular automata. We then describe several techniques to construct reversible cellular automata and a method to determine whether a given one-dimensional automaton is reversible. We present undecidability issues concerning reversible cellular automata and discuss three types of universality: computational universality, intrinsic universality, and physical universality. We finish with short notes about time symmetry, expansiveness, and conservation laws.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s00354-018-0034-6", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1053619", 
        "issn": [
          "0288-3635", 
          "1882-7055"
        ], 
        "name": "New Generation Computing", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "3", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "36"
      }
    ], 
    "name": "Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments", 
    "pagination": "145-172", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "db8673f46e336ee019d1077b8afdd93e544443f34f95bd3ece547e0b02adb303"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s00354-018-0034-6"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1105086529"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s00354-018-0034-6", 
      "https://app.dimensions.ai/details/publication/pub.1105086529"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T10:30", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000349_0000000349/records_113644_00000004.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs00354-018-0034-6"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00354-018-0034-6'


 

This table displays all metadata directly associated to this object as RDF triples.

205 TRIPLES      21 PREDICATES      70 URIs      19 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s00354-018-0034-6 schema:about anzsrc-for:06
2 anzsrc-for:0601
3 schema:author N2fd013bc18e94dc9bb810a5ba37c7cc0
4 schema:citation sg:pub.10.1007/11505877_5
5 sg:pub.10.1007/11523468_34
6 sg:pub.10.1007/978-1-4471-0129-1_6
7 sg:pub.10.1007/978-3-319-58741-7_23
8 sg:pub.10.1007/978-3-319-58741-7_35
9 sg:pub.10.1007/978-3-540-85238-4_34
10 sg:pub.10.1007/978-3-540-92910-9_6
11 sg:pub.10.1007/978-3-642-14034-1
12 sg:pub.10.1007/978-3-642-20712-9_17
13 sg:pub.10.1007/bf01201813
14 sg:pub.10.1007/bf01691062
15 sg:pub.10.1007/bf01857727
16 sg:pub.10.1007/bfb0061728
17 sg:pub.10.1007/s10955-015-1281-2
18 sg:pub.10.1007/s11047-010-9222-0
19 sg:pub.10.1038/scientificamerican1070-120
20 https://app.dimensions.ai/details/publication/pub.1041394511
21 https://doi.org/10.1016/0019-3577(93)90040-6
22 https://doi.org/10.1016/0167-2789(84)90252-5
23 https://doi.org/10.1016/0167-2789(84)90253-7
24 https://doi.org/10.1016/0167-2789(90)90185-r
25 https://doi.org/10.1016/0167-2789(90)90195-u
26 https://doi.org/10.1016/0167-2789(91)90150-8
27 https://doi.org/10.1016/0304-3975(95)00038-x
28 https://doi.org/10.1016/j.jcss.2012.01.006
29 https://doi.org/10.1016/j.tcs.2004.11.021
30 https://doi.org/10.1016/j.tcs.2008.01.041
31 https://doi.org/10.1016/j.tcs.2011.02.023
32 https://doi.org/10.1016/j.tcs.2011.02.024
33 https://doi.org/10.1016/j.tcs.2011.12.037
34 https://doi.org/10.1016/s0022-0000(05)80025-x
35 https://doi.org/10.1016/s0022-0000(72)80009-6
36 https://doi.org/10.1016/s0022-0000(72)80013-8
37 https://doi.org/10.1016/s0022-0000(77)80007-x
38 https://doi.org/10.1016/s0304-3975(96)00081-3
39 https://doi.org/10.1017/cbo9780511549755
40 https://doi.org/10.1090/conm/469/09161
41 https://doi.org/10.1090/psapm/014/9961
42 https://doi.org/10.1090/s0002-9939-1963-0155764-9
43 https://doi.org/10.1103/physrevlett.31.276
44 https://doi.org/10.1142/s0129054195000202
45 https://doi.org/10.1145/2688073.2688107
46 https://doi.org/10.1147/rd.176.0525
47 schema:datePublished 2018-07
48 schema:datePublishedReg 2018-07-01
49 schema:description A cellular automaton is a dynamical system on an infinite array of cells defined by a local update rule that is applied simultaneously at all cells. By carefully choosing the update rule, the global dynamics can be made information preserving. In this case, the cellular automaton is called reversible. In this article, we explain fundamental classical results concerning reversible cellular automata and discuss some more recent developments on selected topics. Classical results reviewed include the Curtis–Hedlund–Lyndon theorem, the Garden-of-Eden theorem and the invariance of uniform Bernoulli distribution under reversible cellular automata. We then describe several techniques to construct reversible cellular automata and a method to determine whether a given one-dimensional automaton is reversible. We present undecidability issues concerning reversible cellular automata and discuss three types of universality: computational universality, intrinsic universality, and physical universality. We finish with short notes about time symmetry, expansiveness, and conservation laws.
50 schema:genre research_article
51 schema:inLanguage en
52 schema:isAccessibleForFree false
53 schema:isPartOf N9e07382794d845e48571becfde892311
54 Nca50e8788c9947b69f0172deac1fb9e2
55 sg:journal.1053619
56 schema:name Reversible Cellular Automata: From Fundamental Classical Results to Recent Developments
57 schema:pagination 145-172
58 schema:productId N2374db8e376041269ccc1b4a5fc86619
59 N419c4aabe33542398baac92fe3507088
60 N8cfc8f73972e47ee815785e244f9705a
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1105086529
62 https://doi.org/10.1007/s00354-018-0034-6
63 schema:sdDatePublished 2019-04-11T10:30
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher N217c4cfdd17c4a39aae48142f257ee9d
66 schema:url https://link.springer.com/10.1007%2Fs00354-018-0034-6
67 sgo:license sg:explorer/license/
68 sgo:sdDataset articles
69 rdf:type schema:ScholarlyArticle
70 N217c4cfdd17c4a39aae48142f257ee9d schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N2374db8e376041269ccc1b4a5fc86619 schema:name doi
73 schema:value 10.1007/s00354-018-0034-6
74 rdf:type schema:PropertyValue
75 N2fd013bc18e94dc9bb810a5ba37c7cc0 rdf:first sg:person.011735452354.35
76 rdf:rest rdf:nil
77 N419c4aabe33542398baac92fe3507088 schema:name dimensions_id
78 schema:value pub.1105086529
79 rdf:type schema:PropertyValue
80 N8cfc8f73972e47ee815785e244f9705a schema:name readcube_id
81 schema:value db8673f46e336ee019d1077b8afdd93e544443f34f95bd3ece547e0b02adb303
82 rdf:type schema:PropertyValue
83 N9e07382794d845e48571becfde892311 schema:issueNumber 3
84 rdf:type schema:PublicationIssue
85 Nca50e8788c9947b69f0172deac1fb9e2 schema:volumeNumber 36
86 rdf:type schema:PublicationVolume
87 anzsrc-for:06 schema:inDefinedTermSet anzsrc-for:
88 schema:name Biological Sciences
89 rdf:type schema:DefinedTerm
90 anzsrc-for:0601 schema:inDefinedTermSet anzsrc-for:
91 schema:name Biochemistry and Cell Biology
92 rdf:type schema:DefinedTerm
93 sg:journal.1053619 schema:issn 0288-3635
94 1882-7055
95 schema:name New Generation Computing
96 rdf:type schema:Periodical
97 sg:person.011735452354.35 schema:affiliation https://www.grid.ac/institutes/grid.1374.1
98 schema:familyName Kari
99 schema:givenName Jarkko
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011735452354.35
101 rdf:type schema:Person
102 sg:pub.10.1007/11505877_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004669217
103 https://doi.org/10.1007/11505877_5
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/11523468_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035438053
106 https://doi.org/10.1007/11523468_34
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/978-1-4471-0129-1_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030314599
109 https://doi.org/10.1007/978-1-4471-0129-1_6
110 rdf:type schema:CreativeWork
111 sg:pub.10.1007/978-3-319-58741-7_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086750862
112 https://doi.org/10.1007/978-3-319-58741-7_23
113 rdf:type schema:CreativeWork
114 sg:pub.10.1007/978-3-319-58741-7_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086750874
115 https://doi.org/10.1007/978-3-319-58741-7_35
116 rdf:type schema:CreativeWork
117 sg:pub.10.1007/978-3-540-85238-4_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032588457
118 https://doi.org/10.1007/978-3-540-85238-4_34
119 rdf:type schema:CreativeWork
120 sg:pub.10.1007/978-3-540-92910-9_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000675121
121 https://doi.org/10.1007/978-3-540-92910-9_6
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/978-3-642-14034-1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041394511
124 https://doi.org/10.1007/978-3-642-14034-1
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/978-3-642-20712-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027023655
127 https://doi.org/10.1007/978-3-642-20712-9_17
128 rdf:type schema:CreativeWork
129 sg:pub.10.1007/bf01201813 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011622046
130 https://doi.org/10.1007/bf01201813
131 rdf:type schema:CreativeWork
132 sg:pub.10.1007/bf01691062 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049449230
133 https://doi.org/10.1007/bf01691062
134 rdf:type schema:CreativeWork
135 sg:pub.10.1007/bf01857727 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032661873
136 https://doi.org/10.1007/bf01857727
137 rdf:type schema:CreativeWork
138 sg:pub.10.1007/bfb0061728 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000307890
139 https://doi.org/10.1007/bfb0061728
140 rdf:type schema:CreativeWork
141 sg:pub.10.1007/s10955-015-1281-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032836701
142 https://doi.org/10.1007/s10955-015-1281-2
143 rdf:type schema:CreativeWork
144 sg:pub.10.1007/s11047-010-9222-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030150049
145 https://doi.org/10.1007/s11047-010-9222-0
146 rdf:type schema:CreativeWork
147 sg:pub.10.1038/scientificamerican1070-120 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007582166
148 https://doi.org/10.1038/scientificamerican1070-120
149 rdf:type schema:CreativeWork
150 https://app.dimensions.ai/details/publication/pub.1041394511 schema:CreativeWork
151 https://doi.org/10.1016/0019-3577(93)90040-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001465095
152 rdf:type schema:CreativeWork
153 https://doi.org/10.1016/0167-2789(84)90252-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024857421
154 rdf:type schema:CreativeWork
155 https://doi.org/10.1016/0167-2789(84)90253-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017085534
156 rdf:type schema:CreativeWork
157 https://doi.org/10.1016/0167-2789(90)90185-r schema:sameAs https://app.dimensions.ai/details/publication/pub.1044244052
158 rdf:type schema:CreativeWork
159 https://doi.org/10.1016/0167-2789(90)90195-u schema:sameAs https://app.dimensions.ai/details/publication/pub.1010901944
160 rdf:type schema:CreativeWork
161 https://doi.org/10.1016/0167-2789(91)90150-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004501638
162 rdf:type schema:CreativeWork
163 https://doi.org/10.1016/0304-3975(95)00038-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1002866933
164 rdf:type schema:CreativeWork
165 https://doi.org/10.1016/j.jcss.2012.01.006 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041095532
166 rdf:type schema:CreativeWork
167 https://doi.org/10.1016/j.tcs.2004.11.021 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008892501
168 rdf:type schema:CreativeWork
169 https://doi.org/10.1016/j.tcs.2008.01.041 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012017670
170 rdf:type schema:CreativeWork
171 https://doi.org/10.1016/j.tcs.2011.02.023 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028506815
172 rdf:type schema:CreativeWork
173 https://doi.org/10.1016/j.tcs.2011.02.024 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035046025
174 rdf:type schema:CreativeWork
175 https://doi.org/10.1016/j.tcs.2011.12.037 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041614651
176 rdf:type schema:CreativeWork
177 https://doi.org/10.1016/s0022-0000(05)80025-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1006334600
178 rdf:type schema:CreativeWork
179 https://doi.org/10.1016/s0022-0000(72)80009-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016636649
180 rdf:type schema:CreativeWork
181 https://doi.org/10.1016/s0022-0000(72)80013-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032327804
182 rdf:type schema:CreativeWork
183 https://doi.org/10.1016/s0022-0000(77)80007-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1046362897
184 rdf:type schema:CreativeWork
185 https://doi.org/10.1016/s0304-3975(96)00081-3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012430781
186 rdf:type schema:CreativeWork
187 https://doi.org/10.1017/cbo9780511549755 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098679392
188 rdf:type schema:CreativeWork
189 https://doi.org/10.1090/conm/469/09161 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089202801
190 rdf:type schema:CreativeWork
191 https://doi.org/10.1090/psapm/014/9961 schema:sameAs https://app.dimensions.ai/details/publication/pub.1089193116
192 rdf:type schema:CreativeWork
193 https://doi.org/10.1090/s0002-9939-1963-0155764-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000280146
194 rdf:type schema:CreativeWork
195 https://doi.org/10.1103/physrevlett.31.276 schema:sameAs https://app.dimensions.ai/details/publication/pub.1060777564
196 rdf:type schema:CreativeWork
197 https://doi.org/10.1142/s0129054195000202 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062897674
198 rdf:type schema:CreativeWork
199 https://doi.org/10.1145/2688073.2688107 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044103794
200 rdf:type schema:CreativeWork
201 https://doi.org/10.1147/rd.176.0525 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063180324
202 rdf:type schema:CreativeWork
203 https://www.grid.ac/institutes/grid.1374.1 schema:alternateName University of Turku
204 schema:name Department of Mathematics and Statistics, University of Turku, 20014, Turku, Finland
205 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...