Detecting and Measuring Randomness in ProcessAlgebraic Computations
Tommaso Bolognesi
Italian National Research Council
A technique is introduced for visually characterizing, by 2D plots, the complexity of processalgebraic 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 processalgebraic diagrams with refined, numeric techniques for measuring their degree of randomness. In particular we explore the application of a densitydependent compressibility measure, based on pointerencoding. 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]


