coopere@rocky2.rockefeller.edu (Ellis D. Cooper) (08/08/90)
STP Abstractions Posted to: sci.math, comp.theory.dynamic-sys I have produced and freely distributed over one hundred pages of words and figures and computer codes to convey the simple intuition of symbol train processing, a <language> using a special kind of graph to describe generation and parallel processing of arbitrary symbolic messages occurring over time. But nothing much has been produced to give rigorous mathematical definitions of STP systems concepts, nor to connect these notions to established mathematical ones. Now I do this by starting with an appeal to analogy with the great theory of ordinary differential equations, their flows, and their dynamical systems. Being far from seriously experienced in that theory, I am relying on my feel for part of The Big Picture as I see it after reading the introduction to differential equations and dynamical systems in [Guckenheimer-Holmes, Nonlinear Oscillations, Dynamical Systems, and Bifurcations of Vector Fields, Springer-Verlag, Ch. 1]. An ordinary differential equation is determined by a linear space of finite dimensions, a vector x consisting of state variables - one for each dimension - and a formula Dx = F(x) for the time rate of change Dx (D = d/dt) expressed as a formula F(x). (Possible dependence of Dx on time would be expressed by Dx = F(x,t). I will not need to speak of this possibility, so I am talking about time independent, <autonomous> systems.) That system of formulas F(x) may be linear in the state variables, in which case the system is a linear system, F(x) = A.x, where A is a linear transformation from the linear state space to itself. The linear system, Dx = A.x, can be solved in a single stroke by calculating its eigen system, which is an easy problem in computable linear algebra. The general solution to Dx = A.x is given by the associated flow map, exp(tA), which moves a given point x of the linear state space along a curve parametrized by t. The eigenspaces of A are invariant subspaces under the flow exp(tA). If you fix the increment of time, say t = T, then the flow map B = exp(TA) is a (smooth) map of the linear state space to itself, and may be iterated at will, so that given a state x the iterations B(x), B(B(x)), B(B(B(x))), etc. form a discrete trajectory in the linear state space. The equation x(n+1) = B(x) is called a discrete dynamical system corresponding to the flow of Dx = A.x and the choice t = T. In the general case, Dx = F(x), the above story can be repeated with respect to the linearizations DF(x) of F(x) at each of the solutions to F(x) = 0, i.e., at the Requilibrium pointsS of the system. In summary, exponentiation of a linear transformation A defines a flow whose invariant subspaces are described by the eigen system of A, and whose motion for equal time jumps gives a discrete dynamical system. A symbol train processing system is like a discrete dynamical system. Given an STP system state, say x, which is determined by the choice of <live state> for each processor and a remaining lifetime for each such choice, the system will pass deterministically through a sequence of STP system states B(x), B(B(x)), B(B(B(x))), etc.. The rule of transition, x to B(x), for STP systems is a computation determined by the GRAPH of the system, by analogy to the determination of a discrete dynamical system from a FORMULA, F(x) or A.x. The analogy ends quickly, though, since unlike the highly developed computable linear algebra machinery available for differential equations, we have no mathematical gadgetry for manipulating and calculating properties of STP systems. This is a problem and an opportunity for new mathematics. The benefit of rigorously exploring the terra incognita of symbol train processing will be to establish improved means of formalizing, simulating and analyzing mental models of real-world phenomena, as explained in the freely available pages of words, pictures, and codes (some in C, and one in Mathematica). For more information, please email your regular mailing address to me. (Note that other STP postings have appeared under comp.ai.neural-nets, comp. visual.lang., and sci.math.symbolic.) Ellis D. Cooper August 6, 1990