Detecting and Measuring Randomness in Process-Algebraic Computations

Tommaso Bolognesi

Italian National Research Council

A technique is introduced for visually characterizing, by 2D plots, the complexity of process-algebraic computations—an area that has not been directly invested, so far, by NKS research. An extension of the familiar notion of functional derivation is proposed, that reveals some interesting properties of this class of plots. Pseudorandom features seem to emerge even for simple subsets of process algebra that are regarded as incapable of universal computations, at least w.r.t. the standard notion of Turing universality. This apparently surprising result suggests to complement the visual inspection of process-algebraic diagrams with refined, numeric techniques for measuring their degree of randomness. In particular we explore the application of a density-dependent compressibility measure, based on pointer-encoding. We have tested this technique by applying it also to the family of elementary cellular automata, where it does indeed prove useful for discriminating between computations, most notably within class 3.

[presentation materials]