Home > Uncategorized > Wolfram-Hilbert sequence in process algebra

Wolfram-Hilbert sequence in process algebra

September 3, 2012 Leave a comment Go to comments

Several techniques for the experimental investigation of the computing power of various formal models, from Cellular Automata to Turing Machines, have been proposed by Stepen Wolfram with his massive ‘New Kind of Science’ (NKS) effort.  Various visual complexity indicators can be used for revealing the emergent ‘internal shapes’ of computations and for nicely exposing their constant, periodic, nested/fractal, pseudo-random, and even more sophisticated dynamics.

Having focused my research activity for over two decades on process algebra and related topics (specifically on the LOTOS specification language, whose definition has been influenced mainly by Milner’s CCS and Hoare’s CSP), when I started looking at the topic of emergence in computation I found it natural to begin by investigating visual complexity indicators for process algebraic languages.

In process algebra the behaviour of a system — usually, a dynamic set of interacting, concurrent entities, or ‘processes’, e.g. a computer communication protocol — is described by an algebraic ‘behavior expression’ – a ‘bex’ – formed by special operators; these are meant to express action, sequentiality, parallelism, synchronization, communication, choice, and so on.

A process algebra always possesses well defined syntax and semantics.  The Structural Operational Semantics of a process algebra formally defines, via axioms and inference rules, the transition relation:

bex — action —> bex’

for any syntactically correct bex.  Note that, for the same bex,  we may well have

bex — otherAction —> otherBex’.

Indeed, in general, behaviors branch, like trees. But when a specifications is deterministic, and we drop the action-labels of the transition relation, the behavior of the specified system reduces to a sequence S = (bex1, bex2, …, bexN, …) of expressions.  If we then code the different behavioral operators by square cells of different color, or different grey level, each bex becomes a finite, 1-D array of such cells; by stacking the cell arrays of all the expressions in sequence S we obtain a pictorial representation of the computation similar to the diagrams used in NKS for illustrating cellular automata behaviors.

In my 2007 JLAP paper (see list of publications) I have studied the power of some fundamental process algebraic operators under this light.  In particular, I have shown that pseudo-random diagrams can be obtained by a subset of process algebraic operators that is provably non-universal, thus providing an argument against Wolfram’s conjecture that pseudo-ramdomness is an indicator of computational universality.

The cited paper also includes a process algebraic specification that simulates Elementary Cellular Automaton 110 (which is universal).

The picture below shows the grey-level-coded deterministic computation of a process algebraic specification of the Hilbert-Wolfram pseudorandom numeric sequence:

a[0]  = 1

a[n+1] =

  • 3/2 * a[n]            if a[n] is even
  • 3/2 * (a[n]+1)     if a[n] is odd.

(The pseudo-randomness of the sequence is apparent by checking, for example, the parities of its elements, which does not seem to follow a defined pattern.)

One can retrieve the a[i]’s by checking the heights of the growing triangular shapes appearing at the right edge of the diagram.

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s