Wolfram Science Group
Phoenix, AZ USA
Registered: Aug 2003
Tommaso Bolognesi paper on Process Algebras
Tommaso Bolognesi, NKS SS 2005, has published a paper on process algebras analysed with NKS methods (with new extensions of those methods) in the Journal of Logic and Algebraic Programming. Of particular interest is his reported find of a set of progress algebra operators that appear to show instrinsic randomness while being provably less than universal.
Behavioral complexity indicators for process algreba: the NKS approach
Several techniques for the experimental investigation of the computing power of various formal models, from cellular automata
to Turing machines, have been proposed by S.Wolfram with his NKS (NewKind of Science).Visual complexity indicators reveal the
â€˜internal shapesâ€™ of computations, and may expose constant, periodic, nested/fractal, pseudo-random, and even more sophisticated
In this paper we investigate visual complexity indicators for process algebra. With its emphasis on reactive, continuously observable behavior, as opposed to input/output behavior, process algebra might appear as an ideal candidate for NKS-style investigations; however, this formal model is in some sense more elaborate than the simple formalisms addressed in NKS, and poses specific problems, such as the presence of both events and states, and the explosive nature of non-determinism.
We consider a set of process algebraic operators and prove its Turing universality by showing that they can emulate any elementary cellular automaton, including n. 110, which is itself universal. The correctness of the emulation is supported by an original visual indicator, which is then used for exploring various subclasses of algebraic expressions and their emergent features. Based on this indicator, and even by restricting to deterministic computations, we have detected and measured, by a data compression technique, the emergence of randomness in a subclass of expressions which is provably not universal.
Besides providing a suggestive visualization of the relative strengths of operator subsets, we believe that results of this type, both of theoretical and of experimental nature, are desirable in light of one of the key NKS conjectures, according to which random-like behavior would be a witness of computational universality.
cite as - T. Bolognesi, Behavioral complexity indicators for process algebra: The NKS approach, J. Log. Algebr. Program. (2007), doi:10.1016/j.jlap.2007.02.004
Report this post to a moderator | IP: Logged