[Tommaso Bolognesi paper on Process Algebras] - A New Kind of Science: The NKS Forum

A New Kind of Science: The NKS Forum

Pages:1


Tommaso Bolognesi paper on Process Algebras

(Click here to view the original thread with full colors/images)


Posted by: Jason Cawley

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

Tommaso Bolognesi

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
dynamics.

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


Posted by: Tony Smith

I've been having a good few days on unrelated fronts and this news only makes it better.

Hopefully everybody can now put that counterproductive conjecture behind them and get back to focusing on techniques for finding efficiently* universal systems within Class 4.

I've said more on this previously.

*where both the rules and the initial data are simple enough that a credible account can be proposed as to how they could have arisen through natural processes.


Posted by: Tony Smith

For Elsevier subscribers or for a US$30 fee, you can get it from http://www.sciencedirect.com/science/journal/15678326

It would be more than a month since I last went looking for it unsuccessfully, and Volume 72, Issue 1 of The Journal of Logic and Algebraic Programming is dated May-June 2007, but I guess that still makes it current news at the rate things have been moving here lately.

Now I just need to find time to read it properly, though that won't stop me mentioning the result in a presentation next week.




Forum Sponsored by Wolfram Research

© 2004-2009 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer
vB Easy Archive Final - Created by Xenon and modified/released by SkuZZy from the Job Openings