Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
A Snapshot of My Life Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

Logical Gates via Gliders Collisions

verfasst von : Genaro J. Martínez, Andrew Adamatzky, Kenichi Morita

Erschienen in: Reversibility and Universality

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

An elementary cellular automaton with memory is a chain of finite state machines (cells) updating their state simultaneously and by the same rule. Each cell updates its current state depending on current states of its immediate neighbours and a certain number of its own past states. Some cell-state transition rules support gliders, compact patterns of non-quiescent states translating along the chain. We present designs of logical gates, including reversible Fredkin gate and controlled not gate, implemented via collisions between gliders.

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 "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

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
Vorheriges Kapitel Power Consumption in Cellular Automata
Nächstes Kapitel Computation and Pattern Formation by Swarm Networks with Brownian Motion
Fußnoten
2
A reproduction of this machine working in rule 110 can be found in http://​uncomp.​uwe.​ac.​uk/​genaro/​rule110/​ctsRule110.​html.
 
Literatur
1.
Adamatzky, A. (ed.): Collision-Based Computing. Springer, Berlin (2002)MATH
2.
Adamatzky, A.: Physarum Machines: Computers from Slime Mould. World Scientific Series on Nonlinear Science Series A, vol. 74. World Scientific, Singapore (2010)
3.
Adamatzky, A.: Fredkin and Toffoli gates implemented in oregonator model of Belousov–Zhabotinsky medium. Int. J. Bifurc. Chaos 27(3), 1750041 (2017)
4.
Adamatzky, A., Mayne, R.: Actin automata: phenomenology and localizations. Int. J. Bifurc. Chaos 25(02), 1550030 (2015)MATHCrossRef
5.
Adamatzky, A., Costello, B.L., Asai, T.: Reaction-Diffusion Computers. Elsevier, Amsterdam (2005)
6.
Albert, J., Culik II, K.: A simple universal cellular automaton and its one-way and totalistic versions. Complex Syst. 1(1), 1–16 (1987)MathSciNetMATH
7.
Baltuska, A., Udem, T., Uiberacker, M., Hentschel, M., Goulielmakis, E., Gohle, C., Holzwarth, R., Yakovlev, V.S., Scrinzi, A., Hansch, T.W., Krausz, F.: Attosecond control of electronic processes by intense light fields. Nature 421(6923), 611–615 (2003)CrossRef
8.
Banks, E.R.: Information and transmission in cellular automata. Ph.D. Dissertion, Cambridge, MA, MIT (1971)
9.
10.
Berlekamp, E.R., Conway, J.H., Guy, R.K.: Winning Ways for your Mathematical Plays, vol. 2. Academic Press, London (1982). (chapter 25)
11.
Ciappina, M.F., Perez-Hernandez, J., Landsman, A., Okell, W., Zherebtsov, S., Frg, B., Schtz, J., Seiffert, L., Fennel, T., Shaaran, T. and Zimmermann, T.: Attosecond physics at the nanoscale. Reports on Progress in Physics (2017)
12.
Codd, E.F.: Cellular Automata. Academic Press Inc, New York (1968)MATH
13.
14.
Davis, M.D., Signal, R., Weyuker, E.J.: Computability, Complexity, and Languages. Computer Science and Scientific Computing, 2nd edn. Academic Press, London (1994)
15.
16.
Fredkin, E., Toffoli, T.: Design Principles for Achieving High-Performance Submicron Digital Technologies, pages 27–46, (2001) (in [2])
17.
Goulielmakis, E., Schultze, M., Hofstetter, M., Yakovlev, V.S., Gagnon, J., Uiberacker, M., Aquila, A.L., Gullikson, E.M., Attwood, D.T., Kienberger, R., Krausz, F.: Single-cycle nonlinear optics. Science 320(5883), 1614–1617 (2008)CrossRef
18.
Hey, A.J.G.: Feynman and Computation: Exploring the Limits of Computers. Perseus Books (1998)
19.
Hutton, T.J.: Codd’s self-replicating computer. Artif. Life 16(2), 99–117 (2010)CrossRef
20.
Jakubowski, M.H., Steiglitz, K., Squier, R.: Computing with solitons: a review and prospectus. Mult. Valued Log. 6(5–6) (2001) (also republished in [2])
21.
Lindgren, K., Nordahl, M.: Universal computation in simple one-dimensional cellular automata. Complex Syst. 4, 229–318 (1990)MathSciNetMATH
22.
23.
Margolus, N.H.: Crystalline computation. In: Hey, A.J.G. (ed.) Feynman and Computation: Exploring the Limits of Computers, pp. 267–305. Perseus Books (1998)
24.
Margolus, N.H.: Universal cellular automata based on the collisions of soft spheres. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 107–134. Springer, Berlin (2002)CrossRef
25.
Margolus, N., Toffoli, T., Vichniac, G.: Cellular-automata supercomputers for fluid dynamics modeling. Phys. Rev. Lett. 56(16), 1694–1696 (1986)CrossRef
26.
Martínez, G.J., Adamatzky, A., McIntosh, H.V.: Phenomenology of glider collisions in cellular automaton rule 54 and associated logical gates. Chaos Solitons Fractals 28, 100–111 (2006)MathSciNetMATHCrossRef
27.
Martínez, G.J., Adamatzky, A., Sanz, R.A.: Complex dynamics of elementary cellular automata emerging in chaotic rule. Int. J. of Bifurcation and Chaos 22(2), 1250023–13 (2012)MATHCrossRef
28.
Martínez, G.J., Adamatzky, A., Sanz, R.A.: Designing Complex Dynamics with Memory. Int. J. Bifurcation and Chaos 23(10), 1330035–131 (2013)MATHCrossRef
29.
Martínez, G.J., Adamatzky, A., McIntosh, H.V.: A computation in a cellular automaton collider rule 110. In: Adamatzky, A. (ed.) Advances in Unconventional Computing Volume 1: Theory, pp. 391–428. Springer, Berlin (2016)
30.
Martínez, G.J., Adamatzky, A., Sanz, R.A., Mora, J.C.S.T.: Complex dynamic emerging in rule 30 with majority memory. Complex Syst. 18(3), 345–365 (2010)MathSciNetMATH
31.
Martínez, G.J., Adamatzky, A., Mora, J.C.S.T., Alonso-Sanz, R.: How to make dull cellular automata complex by adding memory: rule 126 case study. Complexity 15(6), 34–49 (2010)MathSciNet
32.
Martínez, G.J., Adamatzky, A., Stephens, C.R., Hoeflich, A.F.: Cellular automaton supercolliders. Int. J. Mod. Phys. C 22(4), 419–439 (2011)MATHCrossRef
33.
Martínez, G.J., McIntosh, H.V., Mora, J.C.S.T., Vergara, S.V.C.: Reproducing the cyclic tag system developed by Matthew Cook with Rule 110 using the phases f\(_1\)_1. J. Cell. Autom. 6(2–3), 121–161 (2011)
34.
Martínez, G.J., Adamatzky, A., Chen, F., Chua, L.: On soliton collisions between localizations in complex elementary cellular automata: rules 54 and 110 and beyond. Complex Syst. 21(2), 117–142 (2012)MathSciNetMATH
35.
Martínez, G.J., Mora, J.C.S.T., Zenil, H.: Computation and universality: class IV versus class III cellular automata. J. Cell. Autom. 7(5–6), 393–430 (2013)MathSciNetMATH
36.
37.
McIntosh, H.V.: One Dimensional Cellular Automata. Luniver Press, United Kingdom (2009)
38.
39.
Minsky, M.: Computation: Finite and Infinite Machines. Prentice Hall, Englewood Cliffs (1967)MATH
40.
Mitchell, M.: Life and evolution in computers. Hist. Philos. Life Sci. 23, 361–383 (2001)
41.
Moore, C., Mertens, S.: The Nature of Computation. Oxford University Press, Oxford (2011)MATHCrossRef
42.
Moore, P.B., Huxley, H.E., DeRosier, D.J.: Three-dimensional reconstruction of F-actin, thin filaments and decorated thin filaments. J. Mol. Biol. 50(2), 279IN17289–288IN28292 (1970)
43.
Morita, K.: A simple construction method of a reversible finite automaton out of Fredkin gates, and its related problem. Trans. IEICE Jpn. E–73, 978–984 (1990)
44.
Morita, K.: A new universal logic element for reversible computing. IEICE technical report. Theor. Found. Comput. 99(724), 119–126 (2000)
45.
Morita, K.: Simple universal one-dimensional reversible cellular automata. J. Cell. Autom. 2, 159–165 (2007)MathSciNetMATH
46.
47.
Morita, K.: Universality of 8-State reversible and conservative triangular partitioned cellular automata. Lecture Notes in Computer Science, vol. 9863, pp. 45–54. Springer, Cham (2016)
48.
Morita, K., Harao, M.: Computation universality of one-dimensional reversible (injective) cellular automata. Trans. IEICE Jpn. E–72, 758–762 (1989)
49.
Nabekawa, Y., Okino, T., Midorikawa, K.: Probing attosecond dynamics of molecules by an intense a-few-pulse attosecond pulse train. In: 31st International Congress on High-Speed Imaging and Photonics, p. 103280B. International Society for Optics and Photonics (2017)
50.
51.
Post, E.L.: The Two-Valued Iterative Systems of Mathematical Logic. Princeton University Press, Princeton (1941)MATH
52.
Rendell, P.: Turing Machine Universality of the Game of Life. Springer, Berlin (2016)MATHCrossRef
53.
Sanz, R.A.: Cellular Automata with Memory. Old City Publishing, Philadelphia (2009)MATH
54.
55.
Spudich, J.A., Huxley, H.E., Finch, J.T.: Regulation of skeletal muscle contraction: II. Structural studies of the interaction of the tropomyosin-troponin complex with actin. J. Mol. Biol. 72(3), 619IN5IN18621–620IN16IN19632 (1972)
56.
Steiglitz, K.: Soliton-guided quantum information processing. In: Adamatzky, A. (ed.) Advances in Unconventional Computing Volume 2: Prototypes, Models and Algorithms, pp. 297–307. Springer, Berlin (2016)
57.
Steiglitz, K., Kamal, I., Watson, A.: Embedding computation in one-dimensional automata by phase coding solitons. IEEE Trans. Comput. 37(2), 138–145 (1988)MathSciNetCrossRef
58.
Szent-Gyórgyi, A.G.: The early history of the biochemistry of muscle contraction. J. Gen. Physiol. 123(6), 631–641 (2004)CrossRef
59.
Toffoli, T.: Non-conventional computers. In: Webster, J. (ed.) Encyclopedia of Electrical and Electronics Engineering, pp. 455–471. Wiley, London (1998)
60.
Toffoli, T.: Symbol super colliders. In: Adamatzky, A. (ed.) Collision-Based Computing, pp. 1–22. Springer, Berlin (2002)
61.
Tuszyński, J.A., Portet, S., Dixon, J.M., Luxford, C., Cantiello, H.F.: Ionic wave propagation along actin filaments. Biophys. J. 86(4), 1890–1903 (2004)CrossRef
62.
von Neumann, J.: Theory of Self-reproducing Automata (edited and completed by A.W. Burks). University of Illinois Press, Urbana (1966)
63.
64.
65.
Wolfram, S.: Cellular Automata and Complexity. Addison-Wesley Publishing Company, Reading (1994)
66.
Wolfram, S.: A New Kind of Science. Wolfram Media Inc., Champaign (2002)MATH
Metadaten
Titel
Logical Gates via Gliders Collisions
verfasst von
Genaro J. Martínez
Andrew Adamatzky
Kenichi Morita
Copyright-Jahr
2018
Buch
Reversibility and Universality

Print ISBN: 978-3-319-73215-2

Electronic ISBN: 978-3-319-73216-9

Copyright-Jahr: 2018

DOI
https://doi.org/10.1007/978-3-319-73216-9_9