Almost Periodic Configurations on Linear Cellular Automata

• Autorzy: Sutner K.
• Języki publikacji: EN

Abstrakty

EN

We study computational properties of linear cellular automata on configurations that differ from spatially periodic ones in only finitely many places. It is shown that the degree structure of the orbits of cellular automata is the same on these configurations as on the space of finite configurations. We also show that it is undecidable whether the cellular automaton exhibits complicated behavior on configurations of sufficiently long spatial periods and exhibit cellular automata with undecidable orbits whose orbits on backgrounds of all fixed sizes are decidable.

Słowa kluczowe

EN

cellular automata; parallel processing; pattern recognition system; sequential machine theory; machine theory

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 58, nr 3,4
• Strony: 223--240
• Opis fizyczny: Bibliogr. 26 poz., wykr.

Twórcy

autor

Sutner K.

• Computer Sciences Department, Carnegie Mellon University, Pittsburgh, PA 15213, USA,

Bibliografia

• [1] Baldwin, J. Т.: Computation versus Simulation, www.math.uic.edu/~jbaldwin/pub/cafom.ps, July2002.
• [2] Baldwin, J. Т., Shelah. S.: On the Classifiability of Cellular Automata, Theoretical Computer Science, 230(1 -2), 2000, 117-129.
• [3] Codd, E. F.: Cellular Automata, ACM Monograph Series, Academic Press, 1968.
• [4] Davis, M.: A note on universal Turing machines, Princeton University Press, 1956, 167-175.
• [5] Delorme. M.: An Introduction to Cellular Automata, Vol. 460 of Mathematics and Its Applications [6], 1999,5-49.
• [6] Delorme, M., Mazoyer, J.: Cellular Automata: A Parallel Model, vol. 460 of Mathematics and Its Applications, Kluwer Academic Publishers, 1999.
• [7] Durand, B., Róka, Z.: The Game of Life: Universality Revisited, Vol. 460 of Mathematics and Its Applications [6], 1999,51-74.
• [8] Griffor, E. R., Ed.: Handbook of Computability Theory, vol. 140 of Studies in Logic, North-Holland, 1999.
• [9] Hanson, J. E., Cruchfield, J. P.: Computational Mechanics of Cellular Automata, An example, Pysica D, 103, 1997, 169-189.
• [10] II, K. C., Hurd, L. P., Yu, S.: Computation Theoretic Aspects of Cellular Automata, Phvsica D, 45, 1990, 357-378.
• [11] II, K. C., Yu, S.: Undecidability of CA Classification Schemes, Complex Systems, 2(2), 1988, 177-190.
• [12] Lerman. M.: Degrees of Unsolvability, Perspectives in Mathematical Logic, Springer Verlag, 1983.
• [13] Lindgren. C., Nordahl, M.: Universal Computation in Simple One Dimensional Cellular Automata. Complex Systems, 4, 1990. 299-318.
• [14] Rahn, M.: Uuniversalität in Regel 110, http://www. stud.uni-karlsruhe.de/~uypO, March 2003.
• [15] Shore, R. A.: The recursively enumerable degrees, chapter 6. Vol. 140 of Griffor 18], 1999, 169-197.
• [16] Simpson, S. G.: An extension of the recursively enumerable Turing degrees, http: //www.math.psu.edu/simpson/talks/ams0301,2003.
• [17] Soare, R. I.: The Friedberg-Muchnik theorem re-examined. Canad. J. Math., 24, 1972, 1070-1078.
• [18] Soare, R. I.: Recursively Enumerable Sets and Degrees, Perspectives in Mathematical Logic, Springer Verlag, 1987.
• [19] Sutner, K.: A note on Culik-Yu classes, Complex Systems, 3(1), 1989, 107-115.
• [20] Sutner, K.: Classifying Circular Cellular Automata, Physica D. 45(1-3), 1990, 386-395.
• [21] Sutner, K.: De Bruijn Graphs and linear cellular automata, Complex Systems, 5(1), 1991, 19-30.
• [22] Sutner, K.: Linear cellular automata and Fischer automata, Parallel Computing, 23(11), 1997, 1613-1634.
• [23] Sutner, K.: Cellular Automata and Intermediate Reachability Problems, Fundamentae Informaticae, 52(1-3). 2002, 249-256.
• [24] Sutner, K.: Cellular Automata and Intermediate Degrees, Theoretical Computer Science, 296. 2003, 365-375.
• [25] Wolfram, S.: Computation Theory of Cellular Automata, Comm. Math. Physics, 96(1), 1984, 15-57.
• [26] Wolfram, S.: A New Kind of Science, Wolfram Media, 2002.