doi: 10.3934/dcdsb.2021125

Singular function emerging from one-dimensional elementary cellular automaton Rule 150

Department of Mathematics, Kyoto University of Education, Kyoto, 612-8522, Japan

Received  October 2020 Revised  March 2021 Published  April 2021

This paper presents a singular function on the unit interval $ [0, 1] $ derived from the dynamics of one-dimensional elementary cellular automaton Rule $ 150 $. We describe the properties of the resulting function, which is strictly increasing, uniformly continuous, and differentiable almost everywhere, and show that it is not differentiable at dyadic rational points. We also derive functional equations that this function satisfies and show that this function is the only solution of the functional equations.

Citation: Akane Kawaharada. Singular function emerging from one-dimensional elementary cellular automaton Rule 150. Discrete & Continuous Dynamical Systems - B, doi: 10.3934/dcdsb.2021125
References:
[1]

G. Cantor, De la puissance des ensembles parfaits de points: Extrait d'une lettre adressée à l'éditeur [the power of perfect sets of points: Extract from a letter addressed to the editor], Acta Mathematica, 4 (1884), 381-392.  doi: 10.1007/BF02418423.  Google Scholar

[2]

J. C. Claussen, Time evolution of the rule 150 cellular automaton activity from a Fibonacci iteration, Journal of Mathematical Physics, 49 (2008), 062701, 12 pp. doi: 10.1063/1.2939398.  Google Scholar

[3]

D. L. Cohn, Measure Theory, Birkhäuser Basel, second edition, 2013. doi: 10.1007/978-1-4614-6956-8.  Google Scholar

[4]

K. Culik Ⅱ and S. Dube, Fractal and recurrent behavior of cellular automata, Complex Systems, 3 (1989), 253-267.   Google Scholar

[5]

G. de Rham, Sur quelques courbes definies par des equations fonctionnelles, Rendiconti del Seminario Matematico Università e Politecnico di Torino, 16 (1957), 101–113.  Google Scholar

[6]

G. A. Edgar, editor, Classics on Fractals, Studies in Nonlinearity, Addison-Wesley Publishing Company, 1993. Google Scholar

[7]

F. v. HaeselerH.-O. Peitgen and G. Skordev, Cellular automata, matrix substitutions and fractals, Annals of Mathematics and Artificial Intelligence, 8 (1993), 345-362.  doi: 10.1007/BF01530797.  Google Scholar

[8]

M. Hata and M. Yamaguti, The Takagi function and its generalization, Japan Journal of Applied Mathematics, 1 (1984), 183-199.  doi: 10.1007/BF03167867.  Google Scholar

[9]

A. Kawaharada and T. Namiki, Cumulative distribution of rule 90 and Lebesgue's singular function, Proceedings of Automata, 2014 (2014), 165-169.   Google Scholar

[10]

A. Kawaharada, Fractal patterns created by Ulam's cellular automaton, 2014 Second International Symposium on Computing and Networking, (2014), 484–486. doi: 10.1109/CANDAR.2014.51.  Google Scholar

[11]

A. Kawaharada and T. Namiki, Fractal structure of a class of two-dimensional two-state cellular automata, Proceedings of International Workshop on Applications and Fundamentals of Cellular Automata 2017, (2017), 205–208. doi: 10.1109/CANDAR.2017.89.  Google Scholar

[12]

A. Kawaharada and T. Namiki, Relation between spatio-temporal patterns generated by two-dimensional cellular automata and a singular function, International Journal of Networking and Computing, 9 (2019), 354-369.  doi: 10.15803/ijnc.9.2_354.  Google Scholar

[13]

A. Kawaharada and T. Namiki, Number of nonzero states in prefractal sets generated by cellular automata, Journal of Mathematical Physics, 61 (2020), 092702, 17 pp. doi: 10.1063/5.0004652.  Google Scholar

[14]

K. Kawamura, On the set of points where Lebesgue's singular function has the derivative zero, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 87 (2011), 162-166.  doi: 10.3792/pjaa.87.162.  Google Scholar

[15]

K. Kobayashi, On the critical case of Okamoto's continuous non-differentiable functions, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 85 (2009), 101-104.  doi: 10.3792/pjaa.85.101.  Google Scholar

[16]

Z. Łomnicki and S. Ulam, Sur la théorie de la mesure dans les espaces combinatoires et son application au calcul des probabilités i. variables indépendantes, Fundamenta Mathematicae, 23 (1934), 237-278.  doi: 10.4064/fm-23-1-237-278.  Google Scholar

[17]

H. Okamoto, A remark on continuous, nowhere differentiable functions, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 81 (2005), 47-50.  doi: 10.3792/pjaa.81.47.  Google Scholar

[18]

H. Okamoto and M. Wunsch, A geometric construction of continuous, strictly increasing singular functions, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 83 (2007), 114-118.  doi: 10.3792/pjaa.83.114.  Google Scholar

[19]

R. Salem, On some singular monotonic functions which are strictly increasing, Transactions of the American Mathematical Society, 53 (1943), 427-439.  doi: 10.1090/S0002-9947-1943-0007929-6.  Google Scholar

[20]

T. Takagi, A simple example of the continuous function without derivative, Proceedings of the Physico-Mathematical Society of Japan, 1 (1903), 176-177.  doi: 10.11429/subutsuhokoku1901.1.F176.  Google Scholar

[21]

S. Takahashi, Self-similarity of linear cellular automata, Journal of Computer and System Sciences, 44 (1992), 114-140.  doi: 10.1016/0022-0000(92)90007-6.  Google Scholar

[22]

K. Weierstrass, Über continuirliche functionen eines reellen arguments, die für keinen werth des letzeren einen bestimmten differentialquotienten besitzen, Mathematische Werke, 2 (1872), 71–74. (English translation in [6], pages 3–9). doi: 10.1007/978-3-322-91273-2_5.  Google Scholar

[23]

S. J. Willson, Cellular automata can generate fractals, Discrete Applied Mathematics, 8 (1984), 91-99.  doi: 10.1016/0166-218X(84)90082-9.  Google Scholar

[24]

M. Yamaguti, M. Hata and J. Kigami, Mathematics of Fractals, Translations of Mathematical Monographs, American Mathematical Society, 1997. (translated by K. Hudson). doi: 10.1090/mmono/167.  Google Scholar

show all references

References:
[1]

G. Cantor, De la puissance des ensembles parfaits de points: Extrait d'une lettre adressée à l'éditeur [the power of perfect sets of points: Extract from a letter addressed to the editor], Acta Mathematica, 4 (1884), 381-392.  doi: 10.1007/BF02418423.  Google Scholar

[2]

J. C. Claussen, Time evolution of the rule 150 cellular automaton activity from a Fibonacci iteration, Journal of Mathematical Physics, 49 (2008), 062701, 12 pp. doi: 10.1063/1.2939398.  Google Scholar

[3]

D. L. Cohn, Measure Theory, Birkhäuser Basel, second edition, 2013. doi: 10.1007/978-1-4614-6956-8.  Google Scholar

[4]

K. Culik Ⅱ and S. Dube, Fractal and recurrent behavior of cellular automata, Complex Systems, 3 (1989), 253-267.   Google Scholar

[5]

G. de Rham, Sur quelques courbes definies par des equations fonctionnelles, Rendiconti del Seminario Matematico Università e Politecnico di Torino, 16 (1957), 101–113.  Google Scholar

[6]

G. A. Edgar, editor, Classics on Fractals, Studies in Nonlinearity, Addison-Wesley Publishing Company, 1993. Google Scholar

[7]

F. v. HaeselerH.-O. Peitgen and G. Skordev, Cellular automata, matrix substitutions and fractals, Annals of Mathematics and Artificial Intelligence, 8 (1993), 345-362.  doi: 10.1007/BF01530797.  Google Scholar

[8]

M. Hata and M. Yamaguti, The Takagi function and its generalization, Japan Journal of Applied Mathematics, 1 (1984), 183-199.  doi: 10.1007/BF03167867.  Google Scholar

[9]

A. Kawaharada and T. Namiki, Cumulative distribution of rule 90 and Lebesgue's singular function, Proceedings of Automata, 2014 (2014), 165-169.   Google Scholar

[10]

A. Kawaharada, Fractal patterns created by Ulam's cellular automaton, 2014 Second International Symposium on Computing and Networking, (2014), 484–486. doi: 10.1109/CANDAR.2014.51.  Google Scholar

[11]

A. Kawaharada and T. Namiki, Fractal structure of a class of two-dimensional two-state cellular automata, Proceedings of International Workshop on Applications and Fundamentals of Cellular Automata 2017, (2017), 205–208. doi: 10.1109/CANDAR.2017.89.  Google Scholar

[12]

A. Kawaharada and T. Namiki, Relation between spatio-temporal patterns generated by two-dimensional cellular automata and a singular function, International Journal of Networking and Computing, 9 (2019), 354-369.  doi: 10.15803/ijnc.9.2_354.  Google Scholar

[13]

A. Kawaharada and T. Namiki, Number of nonzero states in prefractal sets generated by cellular automata, Journal of Mathematical Physics, 61 (2020), 092702, 17 pp. doi: 10.1063/5.0004652.  Google Scholar

[14]

K. Kawamura, On the set of points where Lebesgue's singular function has the derivative zero, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 87 (2011), 162-166.  doi: 10.3792/pjaa.87.162.  Google Scholar

[15]

K. Kobayashi, On the critical case of Okamoto's continuous non-differentiable functions, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 85 (2009), 101-104.  doi: 10.3792/pjaa.85.101.  Google Scholar

[16]

Z. Łomnicki and S. Ulam, Sur la théorie de la mesure dans les espaces combinatoires et son application au calcul des probabilités i. variables indépendantes, Fundamenta Mathematicae, 23 (1934), 237-278.  doi: 10.4064/fm-23-1-237-278.  Google Scholar

[17]

H. Okamoto, A remark on continuous, nowhere differentiable functions, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 81 (2005), 47-50.  doi: 10.3792/pjaa.81.47.  Google Scholar

[18]

H. Okamoto and M. Wunsch, A geometric construction of continuous, strictly increasing singular functions, Proceedings of the Japan Academy, Series A, Mathematical Sciences, 83 (2007), 114-118.  doi: 10.3792/pjaa.83.114.  Google Scholar

[19]

R. Salem, On some singular monotonic functions which are strictly increasing, Transactions of the American Mathematical Society, 53 (1943), 427-439.  doi: 10.1090/S0002-9947-1943-0007929-6.  Google Scholar

[20]

T. Takagi, A simple example of the continuous function without derivative, Proceedings of the Physico-Mathematical Society of Japan, 1 (1903), 176-177.  doi: 10.11429/subutsuhokoku1901.1.F176.  Google Scholar

[21]

S. Takahashi, Self-similarity of linear cellular automata, Journal of Computer and System Sciences, 44 (1992), 114-140.  doi: 10.1016/0022-0000(92)90007-6.  Google Scholar

[22]

K. Weierstrass, Über continuirliche functionen eines reellen arguments, die für keinen werth des letzeren einen bestimmten differentialquotienten besitzen, Mathematische Werke, 2 (1872), 71–74. (English translation in [6], pages 3–9). doi: 10.1007/978-3-322-91273-2_5.  Google Scholar

[23]

S. J. Willson, Cellular automata can generate fractals, Discrete Applied Mathematics, 8 (1984), 91-99.  doi: 10.1016/0166-218X(84)90082-9.  Google Scholar

[24]

M. Yamaguti, M. Hata and J. Kigami, Mathematics of Fractals, Translations of Mathematical Monographs, American Mathematical Society, 1997. (translated by K. Hudson). doi: 10.1090/mmono/167.  Google Scholar

Figure 1.  Spatio-temporal pattern of Rule $ 150 $, $ \{T_{150} x_o\}_{n = 0}^{31} $
Figure 2.  Limit set of Rule $ 150 $ from the single site seed $ x_o $
Figure 3.  $ \{cum_{150}(n)\} $ of Rule $ 150 $ for $ 0 \leq n < 256 $
Figure 4.  $ F(x) $ and the limit set of Rule $ 150 $
Table 1.  Local rule of Rule $ 150 $
$ x_{i-1} x_i x_{i+1} $ $ 111 $ $ 110 $ $ 101 $ $ 100 $ $ 011 $ $ 010 $ $ 001 $ $ 000 $
$ (T_{150} x)_i $ $ 1 $ $ 0 $ $ 0 $ $ 1 $ $ 0 $ $ 1 $ $ 1 $ $ 0 $
$ x_{i-1} x_i x_{i+1} $ $ 111 $ $ 110 $ $ 101 $ $ 100 $ $ 011 $ $ 010 $ $ 001 $ $ 000 $
$ (T_{150} x)_i $ $ 1 $ $ 0 $ $ 0 $ $ 1 $ $ 0 $ $ 1 $ $ 1 $ $ 0 $
[1]

Petr Kůrka. On the measure attractor of a cellular automaton. Conference Publications, 2005, 2005 (Special) : 524-535. doi: 10.3934/proc.2005.2005.524

[2]

Gelasio Salaza, Edgardo Ugalde, Jesús Urías. Master--slave synchronization of affine cellular automaton pairs. Discrete & Continuous Dynamical Systems, 2005, 13 (2) : 491-502. doi: 10.3934/dcds.2005.13.491

[3]

Yusra Bibi Ruhomally, Muhammad Zaid Dauhoo, Laurent Dumas. A graph cellular automaton with relation-based neighbourhood describing the impact of peer influence on the consumption of marijuana among college-aged youths. Journal of Dynamics & Games, 2021  doi: 10.3934/jdg.2021011

[4]

Hasib Khan, Cemil Tunc, Aziz Khan. Green function's properties and existence theorems for nonlinear singular-delay-fractional differential equations. Discrete & Continuous Dynamical Systems - S, 2020, 13 (9) : 2475-2487. doi: 10.3934/dcdss.2020139

[5]

Manuel Fernández-Martínez. Theoretical properties of fractal dimensions for fractal structures. Discrete & Continuous Dynamical Systems - S, 2015, 8 (6) : 1113-1128. doi: 10.3934/dcdss.2015.8.1113

[6]

Uta Renata Freiberg. Einstein relation on fractal objects. Discrete & Continuous Dynamical Systems - B, 2012, 17 (2) : 509-525. doi: 10.3934/dcdsb.2012.17.509

[7]

Umberto Mosco, Maria Agostina Vivaldi. Vanishing viscosity for fractal sets. Discrete & Continuous Dynamical Systems, 2010, 28 (3) : 1207-1235. doi: 10.3934/dcds.2010.28.1207

[8]

T.K. Subrahmonian Moothathu. Homogeneity of surjective cellular automata. Discrete & Continuous Dynamical Systems, 2005, 13 (1) : 195-202. doi: 10.3934/dcds.2005.13.195

[9]

Achilles Beros, Monique Chyba, Oleksandr Markovichenko. Controlled cellular automata. Networks & Heterogeneous Media, 2019, 14 (1) : 1-22. doi: 10.3934/nhm.2019001

[10]

Michael L. Frankel, Victor Roytburd. Fractal dimension of attractors for a Stefan problem. Conference Publications, 2003, 2003 (Special) : 281-287. doi: 10.3934/proc.2003.2003.281

[11]

Abdon Atangana, Ali Akgül. On solutions of fractal fractional differential equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020421

[12]

Palle E. T. Jorgensen and Steen Pedersen. Orthogonal harmonic analysis of fractal measures. Electronic Research Announcements, 1998, 4: 35-42.

[13]

Marcus Pivato. Invariant measures for bipermutative cellular automata. Discrete & Continuous Dynamical Systems, 2005, 12 (4) : 723-736. doi: 10.3934/dcds.2005.12.723

[14]

Yongjie Wang, Nan Gao. Some properties for almost cellular algebras. Electronic Research Archive, 2021, 29 (1) : 1681-1689. doi: 10.3934/era.2020086

[15]

Oliver Penrose, John W. Cahn. On the mathematical modelling of cellular (discontinuous) precipitation. Discrete & Continuous Dynamical Systems, 2017, 37 (2) : 963-982. doi: 10.3934/dcds.2017040

[16]

Eduardo Ibarguen-Mondragon, Lourdes Esteva, Leslie Chávez-Galán. A mathematical model for cellular immunology of tuberculosis. Mathematical Biosciences & Engineering, 2011, 8 (4) : 973-986. doi: 10.3934/mbe.2011.8.973

[17]

Michael Hochman. Lectures on dynamics, fractal geometry, and metric number theory. Journal of Modern Dynamics, 2014, 8 (3&4) : 437-497. doi: 10.3934/jmd.2014.8.437

[18]

Raffaela Capitanelli, Maria Agostina Vivaldi. Uniform weighted estimates on pre-fractal domains. Discrete & Continuous Dynamical Systems - B, 2014, 19 (7) : 1969-1985. doi: 10.3934/dcdsb.2014.19.1969

[19]

Alexander Plakhov, Vera Roshchina. Fractal bodies invisible in 2 and 3 directions. Discrete & Continuous Dynamical Systems, 2013, 33 (4) : 1615-1631. doi: 10.3934/dcds.2013.33.1615

[20]

Michael Barnsley, James Keesling, Mrinal Kanti Roychowdhury. Special issue on fractal geometry, dynamical systems, and their applications. Discrete & Continuous Dynamical Systems - S, 2019, 12 (8) : i-i. doi: 10.3934/dcdss.201908i

2019 Impact Factor: 1.27

Metrics

  • PDF downloads (11)
  • HTML views (38)
  • Cited by (0)

Other articles
by authors

[Back to Top]