ISSN 2071-8594

Российская академия наук

Главный редактор

Г.С. Осипов

С.В. Гаврилов, И.В. Матюшкин, А.Л. Стемпковский "Вычислимость в клеточных автоматах"

Аннотация.

В обзоре обсуждаются проблемы организации вычислений с помощью клеточных автоматов. Показывается, что общность парадигмы коннекционизма позволяет переносить ряд методов, применимых для нейронных сетей, в предметное поле клеточных автоматов. Специальные вопросы вычислимости рассмотрены на примерах задачи классификации плотности, проблем залпового огня и выбора королевы роя, а также алгоритмов сортировки и алгоритма параллельного умножения Атрубина.

Ключевые слова:

клеточные автоматы, вычислимость, сигнал, сортировка, параллельное умножение, алгоритм Атрубина, машина Тьюринга, времяконструируемость.

Стр. 18-36.

Полная версия статьи в формате pdf.

REFERENCES

1. Anas N. Al-Rabadi, Conservative Reversible Elementary Cellular Automata and their Quantum Computations // In book «Cellular Automata - Innovative Modelling for Science and Engineering», http://cdn.intechopen.com/pdfswm/15007.pdf
2. V.Ye. Tumanov. Osnovy proektirovaniya relyatsionnykh baz dannykh. El.resurs -
http://www.intuit.ru/goods_store/ebooks/8322
3. Gergel V.P., Strongin, R.G. Osnovy parallelnykh vychisleniy dlya mnogoprotsessornykh vychislitelnykh sistem. Uchebnoe posobie – Nizhniy Novgorod: Izd-vo NNGU im. N.I. Lobachevskogo, 2003. 184 s.
4. Alekseev V.Ye., Talanov V.A. Grafy. Modeli vychisleniy. Struktury dannykh: Uchebnik. – Nizhniy Novgorod: Izd-vo NNGU, 2005. 307 s.
5. Stefanova T.S. Otbor soderzhaniya obucheniya neklassicheskim vychislitelnym modelyam // Izvestiya RGPU im. A.I. Gertsena. 2008. №58, s.440-451 URL:
http://cyberleninka.ru/article/n/otbor-soderzhaniyaobucheniya-
neklassicheskim-vychislitelnym-modelyam (data obrashcheniya: 15.04.2015).
6. Anisov A.M. Klassicheskaya vychislimost i priznaki indeterminizma // Logicheskie issledovaniya, #14, 2007, S. 5-26.
7. John E. Savage. VLSI Models of Computation // in e-book “Models of Computation: Exploring the Power of Computing” by John E. Savage, released of July 23, 2008, pp.575-603 -cs.brown.edu/~jes/book/pdfs/ ModelsOfComputation.pdf
8. Carl Hewitt, Peter Bishop, and Richard Steiger. 1973. A universal modular ACTOR formalism for artificial intelligence. In Proceedings of the 3rd international joint conference on Artificial intelligence (IJCAI'73). MorganKaufmannPublishersInc., SanFrancisco, CA, USA,
235-245.
9. Medler, David A. A Brief History of Connectionism. Neural Computing Surveys, 1(2), 1998 – p.18-72.
10. D. E. Rumelhart, J. L. McClelland, and the PDP Research Group, editors. Parallel Distributed Processing, volume 1:Foundations. MIT Press, Cambridge, MA, 1986
11. Wolfram S. A New Kind of Science.- N.Y.: Wolfram Media, 2002.
12. C. Langton, “Computation at the Edge of Chaos,” Physica D, 42:12-37, 1990.
13. Jarkko Kari. Cellular Automata: Tutorial, http://users.utu.fi/jkari/ca/CAintro.pdf
14. Kudryavtsev V., Podkolzin A., Bolotov A. Osnovy teorii odnorodnykh struktur. — Moskva: Moskva, 1990. — S. 296.
15. Aladev V.Z. Klassicheskie odnorodnye struktury. Kletochnye avtomaty. FultusBooks. 2009.
16. J. Kari Theory of cellular automata:A survey/ Theoretical Computer Science 334 (2005) 3 – 33.
17. Zhizn na ploskosti Lobachevskogo, http://habrahabr.ru/post/168421/
18. Margenstern M. Small Universal Cellular Automata in Hyperbolic Spaces. A CollectionofJewels, Springer, 2013, -327 pp.
19. M. Marques-Pita and L.M. Rocha [2008]."Conceptual Structure in Cellular Automata: TheDensity Classification Task".In: Artificial Life XI: Eleventh International Conference on theSimulation and Synthesis of Living Systems, S. Bullock, J. Noble, R. A. Watson, and M. A.Bedau (Eds.). MIT Press, InPress.
20. H. Juillé and J.B. Pollack. “Coevolving the ‘ideal’ trainer: Application to the discovery of cellular automata rules.” In: J.R. Koza, W. Banzhaf, K. Chellapilla, M. Dorigo, D.B. Fogel, M.H. Garzon, D.E. Goldberg, H. Iba and R.L. Riolo (eds.). Genetic Programming 1998: Proceedings of the Third Annual Conference, San Francisco, CA: Morgan Kaufmann, 1998.
21. Christopher Stone, Larry Bull. Solving the Density Classification Task Using Cellular Automaton 184 with Memory //Complex Systems, 18, 2009, pp. 329-34
http://www.complex-systems.com/pdf/18-3-4.pdf
22. R. Alonso-Sanz and L. Bull, “Elementary Coupled Cellular Automata with Memory,” Automata 2008: Theory and Applications of Cellular Automata (A. Adamatzky, R.
Alonso-Sanz, A. Lawniczak, G. J. Martinez, K. Morita, and T. Worsch, eds.), Frome, UK: Luniver Press, 2008 pp.72-99.
23. Gacs, P., Kurdyumov, L., and Levin, L. (1978). Onedimensional uniform arrays that wash out finite islands. Probl. Peredachi. Inform., 14:92–98.
24. Land M., Belew R. K. No perfect two-state cellular automata for density classification exists //Physical review letters. – 1995. – T. 74. – №. 25. – S. 5148.
25. M. Mitchell, J. P. Crutchfield, and P. T. Hraber, “Evolving Cellular Automata to Perform Computations: Mechanisms and Impediments”, Physica D, 75 (1994), 361-391.
26. Yamashita K. et al. The Firing Squad Synchronization Problems for Number Patterns on a Seven-Segment Display and Segment Arrays //IEICE transactions on information and systems.
– 2010. – T. 93. – №. 12. – S. 3276-3283.
27. Umeo H., Nishide K., Kubo K. A simple optimum-time FSSP algorithm for multi-dimensional cellular automata //arXiv preprint arXiv:1208.2761. – 2012.
28. M.V. Ponikarov, Ispolzovanie igr kletochnykh avtomatov dlya sinkhronizatsii v raspredelennykh sistemakh // biznes_informatika №3(05)–2008 g., 31-36
29. Mazoyer J. On optimal solutions to the firing squad synchronization problem //Theoretical Computer Science. – 1996. – T. 168. – №. 2. – S. 367-404.
30. Helene Vivien. An Introduction to CELLULAR AUTOMATA
http://www.liafa.jussieu.fr/~yunes/ca/archives/bookvivien.pdf
31. Mazoyer J., Terrier V. Signals in one-dimensional cellular automata // Theoretical Computer Science, vol.217, 1999, pp.53-80.
32. Iwamoto C. et al. Constructible functions in cellular automata and their applications to hierarchy results //Theoretical Computer Science. – 2002. – T. 270. – №. 1. – S. 797-809.
33. P.C. Fisher, Generation on primes by one dimentional real time iterative array, J. ACM 12 (1965) 388-394.
34. Mahata K., Das S. Gateway node in WSN as the queen bee in a honey bee colony //Communications, Devices and Intelligent Systems (CODIS), 2012 International Conference
on. – IEEE, 2012. – S. 270-273.
35. Banda R. N. D. P. Anonymous Leader Election in Oneand Two-Dimensional Cellular Automata // Student Dissertation Thesis, Comenius University in Bratislava, 2014
- http://peterbanda.net/Peter_Banda-Comenius_Dissertation-
2014.pdf
36. Beckers A., Worsch T.A perimeter–time CA for the queen bee problem //Parallel Computing. – 2001. – T. 27. – №.5. – S. 555-569.
37. Nichitiu C., Mazoyer J., Rémila E. Algorithms for leader election by cellular automata //Journal of Algorithms. – 2001. – T. 41. – №. 2. – S. 302-329.
38. Gornev Ye. S., Matyushkin I. V., Teplov G. S. Analiz kontseptsiy neklassicheskogo kompyutinga i paradig- my konnektsionizma // Elektronnaya tekhnika. Seriya 3: Mikroelektronika. 2015. № 2 (158). S. 45-66.
39. HEEN Olivier, Efficient constant speed-up for one dimensional cellular automata calculators // Parallel Computing 23: pp1663-1671, 1997.
40. ATRUBIN A.J. A one-dimensional real-time iterative multiplier // IEEE Transactions on Electronic Computers EC-14 : pp394-399, 1965.
41. Even S., Litman A. A systematic design and explanation of the Atrubin multiplier //Sequences II. Methods in Communication, Security, and Computer Science –
Springer New York, 1993. – S. 189-202.
42. Bandman O.L. Invarianty kletochno-avtomatnykh modeley reaktsionno-diffuzionnykh protsessov // PDM . 2012. №3. S.108-120.
43. Weimar J.R. Cellular automata for reaction-diffusion systems //Parallel computing. – 1997. – T. 23. – №. 11. – S. 1699-1715.
44. Toffolli T. Cellular automata as an alternative to (rather than approximation of) differential equations in modeling physics // Physica D. 1984. V. 10. P. 117 – 127.
45. Vanag V. K. Issledovanie prostranstvenno raspredelennykh dinamicheskikh sistem metodami veroyatnostnogo kletochnogo avtomata //Uspekhi fizicheskikh nauk. –
1999. – T. 169. – №. 5. – S. 481-505.
46. Paola Flocchini, Vladimir Cezar. Radial View of Continuous Cellular Automata // Fundamenta Informaticae XXI (2001) 1001–1018.
47. Michal Bidlo, ZdenekVasicek, and Karel Slany. Sorting Network Development Using Cellular Automata // In Evolvable Systems: From Biology to Hardware. 9th International
Conference, ICES 2010, York, UK, September 6- 8, 2010, Proceedings, LNCS 6274. London: Springer London, 2010. p. 85-96.
48. Lafe O. Data compression and encryption using cellular automata transforms //Intelligence and Systems, 1996, IEEE International Joint Symposia on. – IEEE, 1996. – S. 234-241.
49. Thomas Zheng. Discrete Orthogonal Transforms Using Cellular Automata // NKS2004 (New Kind of Science Develop), April 22-25, 2004
http://www.wolframscience.com/conference/2004/present
ations/
50. Shaw B., Wong L. C. Algorithmic Self-Assembly of Circuits. – 2002.
51. O.O. Yevsyutin, A.A. Shelupanov Osnovnye podkhody k ispolzovaniyu matematicheskogo apparata teorii kletochnykh avtomatov dlya resheniya zadach kodirovaniya informatsii // Doklady TUSURa, № 2 (32), iyun 2014, S.60-65.
52. Thomas H. Speller. A Study within the Nanosystem Architecture Domain: Self-assembly of Graphene // NKS2007 Conference, July 13, 2007.
53. Speller, T.H., Jr., D. Whitney, and E. Crawley, Using Shape Grammar to Derive Cellular Automata Rule Patterns. Complex Systems, 2007. 17: p. 79-102.
54. White R, Engelen G, Uljee I, 1997, "The use of constrained cellular automata for high-resolution modelling of urban land-use dynamics" Environment and Planning B: Planning and Design 24(3) 323 – 343.
55. Krasnikov G. Y., Matyushkin I. V., Korobov S. V. Visualization of Cellular Automata in Nanotechnology. – 2014. Vol.(3), № 3 S. 98-114.
56. Buchholz T., Klein A., Kutrib M. Real-Time Language Recognition by Alternating Cellular Automata //Proceedings of the International Conference IFIP on Theoretical Computer Science, Exploring New Frontiers of Theoretical Informatics. – Springer-Verlag, 2000. – S. 213-225.
57. Terrier V. Characterization of real time iterative array by alternating device //Theoretical computer science. – 2003. – T. 290. – №. 3. – S. 2075-2084.
58. Gordon D. On the computational power of totalistic cellular automata //Mathematical systems theory. – 1987. – T. 20. – №. 1. – S. 43-52.
59. Jiirgen A., Culik K. A simple universal cellular automaton and its one-way and totalistic version //Complex Systems. – 1987. – T. 1. – S. 1-16.
60. Iwamoto C. et al. Constructible functions in cellular automata and their applications to hierarchy results //Theoretical Computer Science. – 2002. – T. 270. – №. 1. – S. 797-809.
61. A.L. Stempkovsky, P.A. Vlasov, G.V. Kozin. Algorithmic Environment for VLSI Design on Cellular Automata // Proceedings of a Joint Symposium : Information Processing and Software, Systems Design Automation, Academy of Sciences of the USSR, Siemens AG, FRG, Moscow, June 5/6, 1990, Springer-Verlag pp. 308-312.
62. Stempkovskiy A.L., Osipov L.B., Seleznev S.Z. Issledovanie voprosov realizatsii neyroseti po SIP-tekhnologii dlya postroeniya otkazoustoychivykh odnorodnykh arkhitektur. Informatsionnye tekhnologii i vychislitelnye sistemy. - M., 1995, №9, S.58.
63. Stempkovskiy A.L., Osipov L.B., Seleznev S.Z. Problemy realizatsii otkazoustoychivykh arkhitektur neyrochipov po tekhnologii sistem s integratsiey na plastine. Informatsionnye tekhnologii. - M., 1997. №5. S.15.
64. Stempkovskiy A.L. Otkazoustoychivye arkhitektury mikroelektronnykh vychislitelnykh sistem. Informatsionnye tekhnologii i vychislitelnye sistemy. - M., 2001. - № 2-3. S.40.
65. Amoroso S., Cooper G. The Garden-of-Eden theorem for finite configurations //Proceedings of the American Mathematical Society. – 1970. – T. 26. – №. 1. – S. 158-164.
66. Jakubowski M. H. Computing with solitons in bulk media. – PhD, Princeton University, 1999, pp.158.
67. Rennard, Jean-Philippe. Implementation of Logical Functions in the Game of Life. //Adamatzky A. Collision- Based Computing, Springer, pp.491-512, 2002.
68. A.N. Nepeyvoda. Reversivnye vychisleniya: obzor mirovogo opyta // Materialy konferentsii «Parallelnye vychisleniya i zadachi upravleniya», Moskva,
24-26 oktyabrya 2012, A204 -
http://paco2012.ipu.ru/procdngs/A204.pdf