wolframscience.com

A New Kind of Science: The NKS Forum : Powered by vBulletin version 2.3.0 A New Kind of Science: The NKS Forum > News & Announcements > Tommaso Bolognesi paper on Process Algebras
  Last Thread   Next Thread
Author
Thread Post New Thread    Post A Reply
Jason Cawley
Wolfram Science Group
Phoenix, AZ USA

Registered: Aug 2003
Posts: 712

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

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

Report this post to a moderator | IP: Logged

Old Post 03-26-2007 06:39 PM
Jason Cawley is offline Click Here to See the Profile for Jason Cawley Click here to Send Jason Cawley a Private Message Edit/Delete Message Reply w/Quote
Tony Smith
Meme Media
Melbourne, Australia

Registered: Oct 2003
Posts: 168

Good

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.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Old Post 03-27-2007 11:34 AM
Tony Smith is offline Click Here to See the Profile for Tony Smith Click here to Send Tony Smith a Private Message Visit Tony Smith's homepage! Edit/Delete Message Reply w/Quote
Tony Smith
Meme Media
Melbourne, Australia

Registered: Oct 2003
Posts: 168

Tommaso Bolognesi's paper available online

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.

__________________
Tony Smith
Complex Systems Analyst
TransForum developer
Local organiser

Report this post to a moderator | IP: Logged

Old Post 06-24-2007 12:43 PM
Tony Smith is offline Click Here to See the Profile for Tony Smith Click here to Send Tony Smith a Private Message Visit Tony Smith's homepage! Edit/Delete Message Reply w/Quote
Post New Thread    Post A Reply
  Last Thread   Next Thread
Show Printable Version | Email this Page | Subscribe to this Thread


 

wolframscience.com  |  wolfram atlas  |  NKS online  |  web resources  |  contact us

Forum Sponsored by Wolfram Research

© 2004-14 Wolfram Research, Inc. | Powered by vBulletin 2.3.0 © 2000-2002 Jelsoft Enterprises, Ltd. | Disclaimer | Archives