Chapter 7 - Physical and computational analysis of symbolic signals

Summary

The emphasis in the previous part of the book was on mathematical tools that permit the classification of symbolic signals in a general and accurate way by means of a few numbers or functions. The study of complexity, however, cannot be restricted to the evaluation of indicators alone, since each of them presupposes a specific model which may or may not adhere to the system. For example, power spectra hint at a superposition of periodic components, fractal dimensions to a self-similar concentration of the measure, the thermodynamic approach to extensive Hamiltonian functions. It seems, hence, necessary to seek procedures for the identification of appropriate models before discussing definite complexity measures. Stated in such a general form, the project would be far too ambitious (tantamount to finding “meta-rules” that select physical theories). The symbolic encoding illustrated in the previous chapters provides a homogeneous environment which makes the general modelling question more amenable to an effective formalization.

Independent efforts in the study of neuron nets, compiler programs, mathematical logic, and natural languages have led to the construction of finite discrete models (automata) which produce symbolic sequences with different levels of complexity by performing elementary operations. The corresponding levels of computational power are well expressed by the Chomsky hierarchy, a list of four basic families of automata culminating in the celebrated Turing machine.