Skip to main content
SpringerLink
Log in

Annealed and quenched inhomogeneous cellular automata (INCA)

  • Articles
  • Published:
Journal of Statistical Physics Aims and scope Submit manuscript

Abstract

A probabilistic one-dimensional cellular automaton model by Domany and Kinzel is mapped into an inhomogeneous cellular automaton with the Boolean functions XOR and AND as transition rules. Wolfram's classification is recovered by varying the frequency of these two simple rules and by quenching or annealing the inhomogeneity. In particular, “class 4” is related to critical behavior in directed percolation. Also, the critical slowing down of second-order phase transitions is related to a stochastic version of the classical “halting problem” of computation theory.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

We’re sorry, something doesn't seem to be working properly.

Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Similar content being viewed by others

References

  1. C. H. Bennett and G. Grinstein,Phys. Rev. Lett. 55:657–660 (1985).

    Google Scholar 

  2. A. W. Burks,Essays on Cellular Automata (University of Illinois Press, 1970).

  3. E. Domany and W. Kinzel,Phys. Rev. Lett 53 311–314 (1984).

    Google Scholar 

  4. D. Farmer, T. Toffoli, and S. Wolfram (eds.), Cellular automata,Physica D 10 (1–2) (1984);Cellular Automata (North-Holland, 1984).

  5. P. Gacs and J. Reif, inProceedings of the Seventeenth ACM Symposium on the Theory of Computing, Providence, R.I., 1985 (ACM, 1985), pp. 388–395.

  6. G. Grinstein, C. Jayaprakash, and Yu He,Phys. Rev. Lett. 55:2527–2530 (1985).

    Google Scholar 

  7. H. Hartman and G. Y. Vichniac, inDisordered Systems and Biological Organization, E. Bienenstock, F. Fogelman, and G. Weisbuch, eds. (Springer-Verlag, 1986).

  8. B. Hayes,Sci. Am. 250(3):12–21 (1984).

    Google Scholar 

  9. S. A. Kauffman,Physica D 10:145–156 (1984).

    Google Scholar 

  10. W. Kinzel,Z. Phys. B 58:229–244 (1985).

    Google Scholar 

  11. W. Kinzel and J. M. Yeomans,J. Phys. A 14:L163-L168 (1981).

    Google Scholar 

  12. M. L. Minsky,Computation: Finite and Infinite Machines (Prentice-Hall, 1967).

  13. A. L. Toom, inLocally Interacting Systems and Their Applications in Biology, R. L. Dobrushin, V. I. Kryukov, and A. L. Toom, eds., Lectures Notes in Mathematics, No. 653 (Springer-Verlag, 1978); inMulticomponent Random Systems, R. L. Dobrushin, ed.,Advances in Probabilities, Vol. 6 (Dekker, 1980), pp. 549–575.

  14. J. von Neumann,Theory of Self-Reproducing Automata [ed. and completed by A. W. Burks], (University of Illinois Press, 1966).

  15. S. Wolfram,Physica D 10:1–35 (1984).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Laboratory for Computer Science, Massachusetts Institute of Technology, 02139, Cambridge, Massachusetts

    G. Y. Vichniac & P. Tamayo

  2. Department EAPS, Massachusetts Institute of Technology, 02139, Cambridge, Massachusetts

    H. Hartman

Authors
  1. G. Y. Vichniac
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. P. Tamayo
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. H. Hartman
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Vichniac, G.Y., Tamayo, P. & Hartman, H. Annealed and quenched inhomogeneous cellular automata (INCA). J Stat Phys 45, 875–883 (1986). https://doi.org/10.1007/BF01020578

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF01020578

Key words

Search

Navigation