nach oben

New Generation Computing

Erschienen in:

09.01.2022

The Weak Universality of Two-Dimensional Five-State von Neumann Neighborhood Number-Conserving Cellular Automaton

verfasst von: Hisamichi Ishizaka, Gil-Tak Kong, Katsunobu Imai

Erschienen in: New Generation Computing | Ausgabe 2/2022

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We study the computing abilities of small-state rotation symmetric von Neumann neighborhood NCCAs (RNCAs). It is known that such RNCAs with four states or less are trivial and any 5-state RNCAs cannot be strongly universal. In this paper, we show there is a weakly-universal 5-state RNCA, i.e., it is possible to simulate any combinational logic circuit. We also show a configuration which simulates the rule 110 cellular automaton.

Vorheriger Artikel Helmholtz: A Verifier for Tezos Smart Contracts Based on Refinement Types

Nächster Artikel Replication of Arbitrary Hole-Free Shapes via Self-assembly with Signal-Passing Tiles

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

This is the von Neumann neighborhood.

Banks, E.R.: Universality in cellular automata. In: 11th Annual Symposium on Switching and Automata Theory (swat 1970), pp. 194–215 (1970)

Boccara, N., Fukś, H.: Number-conserving cellular automaton rules. Fundam. Inform. 52(1–3), 1–13 (2002)MathSciNetMATH

Codd, E.F.: Cellular Automata. ACM Monograph Series, Academic Press, Cambridge (1968)MATH

Cook, M.: Universality in elementary cellular automata. Complex Syst. 15(1), 1–40 (2004)MathSciNetMATH

Durand, B., Formenti, E., Róka, Z.: Number-conserving cellular automata I: decidability. Theor. Comput. Sci. 1–3(299), 523–535 (2003)MathSciNetCrossRef

Imai, K., Ishizaka, H., Poupet, V.: 5-State rotation-symmetric number-conserving cellular automata are not strongly universal. In: Proceedings of the International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2014), pp. 31–43. Springer, Cham (2014)MATH

Moreira, A.: Universality and decidability of number-conserving cellular automata. Theor. Comput. Sci. 292(3), 711–721 (2003)MathSciNetCrossRef

Morita, K., Tojima, Y., Imai, K., Ogiro, T.: Universal computing in reversible and number-conserving two-dimensional cellular spaces. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 161–199. Springer, Berlin (2002)CrossRef

Nagel, K., Schreckenberg, M.: A cellular automaton model for freeway traffic. Journal de Physique I 2(12), 2221–2229 (1992)CrossRef

10.

Serizawa, T.: Three-state Neumann neighbor cellular automata capable of constructing self-reproducing machines. Syst. Comput. Jpn. 18(4), 33–40 (1987)CrossRef

11.

Tanimoto, N., Imai, K.: A characterization of von Neumann neighbor number-conserving cellular automata. J. Cell. Autom. 4(1), 39–54 (2009)MathSciNetMATH

12.

Tanimoto, N., Imai, K., Iwamoto, C., Morita, K.: On the non-existance of rotation-symmetric von Neumann neighbor number-conserving cellular automata of which the state number is less than four. IEICE Trans. 92-D(2), 255–257 (2009)

Titel: The Weak Universality of Two-Dimensional Five-State von Neumann Neighborhood Number-Conserving Cellular Automaton
verfasst von: Hisamichi Ishizaka
Gil-Tak Kong
Katsunobu Imai
Publikationsdatum: 09.01.2022
Verlag: Ohmsha
Erschienen in: New Generation Computing / Ausgabe 2/2022
Print ISSN: 0288-3635
Elektronische ISSN: 1882-7055
DOI: https://doi.org/10.1007/s00354-021-00150-2

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2022

Chemical Reaction Regular Grammars

On the Computational Power of Phosphate Transfer Reaction Networks

Helmholtz: A Verifier for Tezos Smart Contracts Based on Refinement Types

Monotone Control of R Systems

DNA Concentration Regulator That can be Driven for a Long Time

Codensity Games for Bisimilarity

Premium Partner