На главную страницу НМУ

А.Л.Тоом (A.Toom)

Клеточные автоматы (Cell automata)

(миникурс в сентябре)

Course notes (in English)

[Gzipped postscript (166K)|Zipped postscript (166K)]

1. A definition of cellular automata. Theorem of existence of an invariant measure. Coupling and a sufficient condition of ergodicity. [1,2]
2. Algoritmic unsolvability of the problem of ergodicity for cellular automata and some other unsolvable problems. [1,3,4,5,6]
3. Stavskaya process. Proof based on duality of oriented planat graphs. Properties of the invariant measure. [1,7,8,9]
4. Some growth models. [14,15]
5. Eroders and their criterion based on convex sets and Helly theorem. Galperin's theory. [10,12,13]
6. Non-Gibbsianness of the invariant measures of some cellular automata. [16]
7. Non-symmetric systems with variable length. Comparison with contact processes. [17,18]
8. Symmetric systems with variable length. Spontaneous symmetry breaking. [19]

Литература

1. Discrete Local Markov Systems. A. Toom, N. Vasilyev, O. Stavskaya, L. Mityushin, G. Kurdyumov and S. Pirogov. {\it Stochastic Cellular Systems : ergodicity, memory, morphogenesis}. Ed. by R. Dobrushin, V. Kryukov and A. Toom. Nonlinear Science: theory and applications, Manchester University Press, \Y{1990}, pp. 1-182.
2. A. Toom. Cellular Automata with Errors: Problems for Students of Probability. {\it Topics in Contemporary Probability and its Applications.} Ed. J. Laurie Snell. Series {\it Probability and Stochastics} ed. by Richard Durrett and Mark Pinsky. CRC Press, \Y{1995}, pp. 117-157.
3. N. Petri. The unsolvability of the problem of discerning of annuling iterative nets. {\it Research in the Theory of Algorithms and Mathematical Logic}, Moscow, Nauka, 1979 (in Russian).
4. A. Toom and L. Mityushin. Two Results regarding Non-Computability for Univariate Cellular Automata. {\it Problems of Information Transmission}, \Y{1976}, v. 12, n. 2, pp. 135-140. (Originally published in Russian.)
5. A. Toom. Algorithmical unsolvability of the ergodicity problem for locally interacting processes with continuous time. {\it \JSP}, vol. 98, 1/2, \Y{2000}, pp. 495-501.
6. A. Toom. Algorithmical unsolvability of the ergodicity problem for binary cellular automata. {\it Markov Processes and Related Fields}, v. 6, n. 4, \Y{2000}, pp. 569-577.
7. O. Stavskaya and I. Piatetsky-Shapiro. Uniform networks of spontaneously active elements. {\it Problemy kiberrnetiki,} 20, pp. 91-106, \Y{1968}.
8. A. Toom. A Family of Uniform Nets of Formal Neurons. {\it Soviet Math. Doklady}, \Y{1968}, v.9 n.6, pp. 1338-1341. (Originally published in Russian.)
9. A. Toom. On Invariant Measures in Non-Ergodic Random Media. {\it Probabilistical Methods of Investigation }, issue 41. Ed. by A. Kolmogorov. Moscow University Press, \Y{1972}, pp. 43-51. (Only in Russian.)
10. A. Toom. Non-Ergodic Multidimensional Systems of Automata. {\it Problems of Information Transmission}, \Y{1974}, v. 10, pp. 239-246. (Originally published in Russian.)
11. A. Toom. Monotonic Binary Cellular Automata. {\it Problems of Information Transmission}, \Y{1976}, v. 12, n. 1, pp. 33-37. (Originally published in Russian.)
12. A. Toom. Stable and Attractive Trajectories in Multicomponent Systems. {\it Multicomponent Random Systems}, ed. by R. Dobrushin and Ya. Sinai. Advances in Probability and Related Topics, Dekker, \Y{1980}, v. 6, pp. 549-576. (Originally published in Russian in the volume ``Multicomponent Random Systems'', Nauka, Moscow, \Y{1978}, pp. 288-308.)
13. G. Galperin. One-dimensional local monotone operators with memory. {\it Soviet Math. Docl.}, 17(3), pp. 688-692, \Y{1976}.
14. A. Toom. On Critical Phenomena in Interacting Growth Systems. Part I: General. {\it \JSP}, \Y{1994}, v. 74, n. 1/2, pp. 91-109.
15. A. Toom. On Critical Phenomena in Interacting Growth Systems. Part II: Bounded Growth. {\it \JSP}, \Y{1994}, v. 74, n. 1/2, pp. 111-130.
16. R. Fern\'andez and A. Toom. Non-Gibbsianness of the invariant measures of non-reversible cellular automata with totally asymmetric noise. {\it Geometric Methods in Dynamics (II): Volume in Honor of Jacob Palis. Ast\'erisque}, v. 287, December \Y{2003}, pp. 71-87. % ISBN 2-85629-139-2.
17. A. Toom. Particle systems with variable length. {\it Bulletin of the Brazilian Mathematical Society}, v. 33, n. 3, November \Y{2002}, pp. 419-425.
18. A. Toom. Non-ergodicity in a 1-D particle process with variable length. {\it \JSP}, vol. 115, \Y{2004}, nn. 3/4, pp. 895-924.
19. A. Toom. Spontaneous symmetry breaking in a process with variable length. Preprint.