- Access by Xinjiang University
Sensitivity to noise and ergodicity of an assembly line of cellular automata that classifies density
Phys. Rev. E 83, 031112 – Published 11 March, 2011
DOI: https://doi.org/10.1103/PhysRevE.83.031112
Abstract
We investigate the sensitivity of the composite cellular automaton of H. Fukś [Phys. Rev. E 55, R2081 (1997)] to noise and assess the density classification performance of the resulting probabilistic cellular automaton (PCA) numerically. We conclude that the composite PCA performs the density classification task reliably only up to very small levels of noise. In particular, it cannot outperform the noisy Gacs-Kurdyumov-Levin automaton, an imperfect classifier, for any level of noise. While the original composite CA is nonergodic, analyses of relaxation times indicate that its noisy version is an ergodic automaton, with the relaxation times decaying algebraically over an extended range of parameters with an exponent very close (possibly equal) to the mean-field value.
Article Text
References (22)
- S. Wolfram, Cellular Automata and Complexity: Collected Papers (Addison-Wesley, Reading, MA, 1994).
- T. Toffoli and N. Margolus, Cellular Automata Machines: A New Environment for Modeling (MIT, Cambridge, MA, 1987).
- P. Sarkar, ACM Comput. Surv. 32, 80 (2000).
- P. Gács, G. L. Kurdyumov, and L. A. Levin, Probl. Inform. Transm. 14, 223 (1978).
- P. Gonzaga de Sá and C. Maes, J. Stat. Phys. 67, 507 (1992).
- M. Land and R. K. Belew, Phys. Rev. Lett. 74, 5148 (1995).
- M. S. Capcarrere, M. Sipper, and M. Tomassini, Phys. Rev. Lett. 77, 4969 (1996).
- M. Mitchell, J. P. Crutchfield, and P. T. Hraber, Physica D 75, 361 (1994).
- R. Das, M. Mitchell, and J. P. Crutchifeld, in Parallel Problem Solving from Nature – PPSN III: Proceedings of the International Conference on Evolutionary Computation, edited by Y. Davidor, H.-P. Schwefel, and R. Männer, Lect. Notes Comput. Sci. Vol. 866 (Springer, Berlin, 1994), pp. 344–353.
- D. Andre, F. H. Bennett III, and J. R. Koza, in Genetic Programming 1996: Proceedings of the First Annual Conference, edited by J. R. Koza, D. E. Goldberg, D. B. Fogel, and R. L. Riolo (MIT, Cambridge, MA, 1996), pp. 3–11.
- J. P. Crutchifeld and M. Mitchell, Proc. Natl. Acad. Sci. USA 92, 10742 (1995).
- H. Juillé and J. B. Pollack, in Genetic Programming 1998: Proceedings of the Third Annual Conference, edited by J. R. Koza, W. Banzhaf, K. Chellapilla, M. Dorigo, D. B. Fogel, M. H. Garzon, D. E. Goldberg, H. Iba, and R. L. Riolo (Morgan Kaufmann, San Francisco, 1998), pp. 519–527.
- J. R. Koza, F. H. Bennett III, D. Andre, and M. A. Keane, Genetic Programming III: Darwinian Invention and Problem Solving (Morgan Kaufmann, San Francisco, 1999), Chap. 58.
- H. Fukś, Phys. Rev. E 55, R2081 (1997).
- H. F. Chau, K. K. Yan, K. Y. Wan, and L. W. Siu, Phys. Rev. E 57, 1367 (1998); H. F. Chau, L. W. Siu, and K. K. Yan, Int. J. Mod. Phys. C 10, 883 (1999).
- J. J. Binney, N. J. Dowrick, A. J. Fisher, and M. E. J. Newman, The Theory of Critical Phenomena (Clarendon, Oxford, 1992).
- J. Marro and R. Dickman, Nonequilibrium Phase Transitions in Lattice Models (Cambridge University, Cambridge, 1999).
- M. Tomassini, M. Giacobini, and C. Darabos, in Parallel Problem Solving from Nature – PPSN VIII: Proceedings of the 8th International Conference, edited by X. Yao, E. Burke, J. A. Lozano, J. Smith, J. J. Merelo-Guervós, J. A. Bullinaria, J. Rowe, P. Tino, A. Kabán, and H.-P. Schwefel, Lect. Notes Comput. Sci. Vol. 3242 (Springer, Berlin, 2004), pp. 672–681.
- C. Darabos, M. Giacobini, and M. Tomassini, in Cellular Automata: Proceedings of the 7th International Conference on Cellular Automata for Research and Industry, edited by S. El Yacoubi, B. Chopard, and S. Bandini, Lect. Notes Comput. Sci. Vol. 4173 (Springer, Berlin, 2006), pp. 512–521.
- A. A. Moreira, A. Mathur, D. Diermeier, and L. A. N. Amaral, Proc. Natl. Acad. Sci. USA 101, 12085 (2004); S. M. D. Seaver, A. A. Moreira, M. Sales-Pardo, R. D. Malmgren, D. Diermeier, and L. A. N. Amaral, Eur. J. Phys. B 67, 369 (2009).
- B. Mesota and C. Teuscherb, Physica D 211, 88 (2005).
- P. Balister, B. Bollobás, and R. Kozma, Random Struct. Algor. 29, 399 (2006); P. Balister, B. Bollobás, J. R. Johnson, and M. Walters, ibid. 36, 315 (2010).