Continuous spatial automaton: Difference between revisions

Revision as of 02:00, 6 October 2007

Latest revision as of 04:38, 13 March 2025

(29 intermediate revisions by 22 users not shown)

Line 1:

{{short description|Abstract machines which have a continuum of locations with finite states}}

'''Continuous spatial automata''', unlike [[cellular automata]], have a continuum of locations. The state of a ___location is a finite number of real numbers. Time is also continuous, and the state evolves according to differential equations. One important example is [[reaction-diffusion]] textures, differential equations proposed by [[Alan Turing]] to explain how chemical reactions could create the stripes on [[zebra]]s and spots on leopards. When these are approximated by CA, such CAs often yield similar patterns. MacLennan [http://www.cs.utk.edu/~mclennan/contin-comp.html] considers continuous spatial automata as a model of computation.

A '''continuous spatial automaton''' is a type of computer model studied in [[automata theory]], a subfield of [[computer science]]. It is similar to a [[cellular automaton]], in that it models the evolution of a set of many states over time. Unlike a cellular automaton, which has a discrete grid of states, a continuous spatial automaton has a continuum of locations in one or more dimensions. The state at each ___location may be chosen from a discrete set of numbers, or from a continuous interval of [[real number]]s. The states may also vary continuously in time, and in this case the state evolves according to a [[differential equation]].

There are known examples of continuous spatial automata which exhibit propagating phenomena analogous to gliders in [[Conway's Game of Life]]. For example, take a [[2-sphere]], and attach a handle between two nearby points on the equator; because this manifold has [[Euler characteristic]] zero, we may choose a continuous nonvanishing vector field pointing through the handle, which in turns implies the existence of a [[Lorentz metric]] such that the equator is a closed [[timelike]] [[geodesic]]. An observer free falling along this geodesic falls toward and through the handle; in the observer's [[frame of reference]], the handle propagates toward the observer. This example generalizes to any [[Lorentzian manifold]] containing a closed timelike geodesic which passes through relatively flat region before passing through a relatively curved region. Because no [[closed timelike curve]] on a Lorentzian manifold is [[timelike homotopic]] to a point (where the manifold would not be locally causally well behaved), there is some [[timelike topological feature]] which prevents the curve from being deformed to a point. Because it has been conjectured that these might serve as a model of a photon, these are sometimes also called [[pseudo-photons]].

One important example is [[reaction–diffusion]] textures, differential equations proposed by [[Alan Turing]] to explain how chemical reactions could create the stripes on [[zebra]]s and spots on [[leopard]]s. When these are approximated by cellular automata, such cellular automata often yield similar patterns. Another important example is neural fields, which are the [[continuum limit]] of [[Neural network (biology)|neural networks]] where average firing rates evolve based on [[integro-differential equation]]s.<ref>H. R. Wilson and J. D. Cowan. "Excitatory and inhibitory interactions in localized populations of model neurons" ''Biophysical Journal'', 12:1–24, 1972.</ref><ref>H. R. Wilson and J. D. Cowan. "A mathematical theory of the functional dynamics of cortical and thalamic nervous tissue" ''Kybernetik'', 13:55–80, 1973.</ref> Such models demonstrate [[spatiotemporal pattern]] [[pattern formation|formation]], localized states and [[travelling wave]]s.<ref>S. Amari. "Dynamics of pattern formation in lateral inhibition type neural fields" ''Biological Cybernetics'', 27:77–87, 1977.</ref><ref>{{Cite journal|doi = 10.4249/scholarpedia.1373|title = Neural fields|year = 2006|last1 = Coombes|first1 = Stephen|journal = Scholarpedia|volume = 1|issue = 6|page = 1373|bibcode = 2006SchpJ...1.1373C| doi-access=free| s2cid=33785752 }}</ref> They have been used as models for cortical memory states and visual hallucinations.<ref>G. B. Ermentrout and J. D. Cowan. "A mathematical theory of visual hallucination patterns" ''Biological Cybernetics'', 34:137–150, 1979.</ref>

Bruce MacLennan considers continuous spatial automata as a model of computation, and demonstrated that they can implement Turing-universality.<ref>David H. Wolpert and Bruce J. MacLennan, [http://web.eecs.utk.edu/~mclennan/papers/ut-cs-93-206.pdf "A Universal Field Computer That is Purely Linear"], University of Tennessee, Knoxville, Department of Computer Science Technical Report CS-93-206, September 14, 1993, 28 pp. </ref>

==See also==

*[[Analog computer]]

*[[Coupled map lattice]]

==References==

{{Reflist}}

It is an important open question whether pseudo-photons can be created in an Einstein vacuum space-time, in the same way that a [[glider gun]] in Conway's Game of Life fires off a series of gliders. If so, it is argued that pseudo-photons can be created and destroyed only in multiples of two, as a result of energy-momentum conservation.

[[Category:Cellular automata]]