Statistical Complexity Analysis of Turing Machine tapes with Fixed Algorithmic Complexity Using the BestOrder Markov Model Sources that generate symbolic sequences with algorithmic nature may differ in statistical complexity because they create structures that follow algorithmic schemes, rather than generating symbols from a probabilistic function assuming independence. In the case of Turing machines, this means that machines with the same algorithmic complexity can create tapes with different statistical complexity. In this paper, we use a compressionbased approach to measure global and local statistical complexity of specific Turing machine tapes with the same number of states and alphabet. Both measures are estimated using the bestorder Markov model. For the global measure, we use the Normalized Compression (NC), while, for the local measures, we define and use normal and dynamic complexity profiles to quantify and localize lower and higher regions of statistical complexity. We assessed the validity of our methodology on synthetic and real genomic data showing that it is tolerant to increasing rates of editions and block permutations. Regarding the analysis of the tapes, we localize patterns of higher statistical complexity in two regions, for a different number of machine states. We show that these patterns are generated by a decrease of the tapexe2x80x99s amplitude, given the setting of small rule cycles. Additionally, we performed a comparison with a measure that uses both algorithmic and statistical approaches (BDM) for analysis of the tapes. Naturally, BDM is efficient given the algorithmic nature of the tapes. However, for a higher number of states, BDM is progressively approximated by our methodology. Finally, we provide a simple algorithm to increase the statistical complexity of a Turing machine tape while retaining the same algorithmic complexity. We supply a publicly available implementation of the algorithm in C language under the GPLv3 license. All results can be reproduced in full with scripts provided at the repository.

Dynamics and Complexity of Computrons We investigate chaoticity and complexity of a binary general network automata of finite size with external input which we call a computron. As a generalization of cellular automata, computrons can have nonuniform cell rules, nonregular cell connectivity and an external input. We show that any finitestate machine can be represented as a computron and develop two novel settheoretic concepts: (i) diversity space as a metric space that captures similarity of configurations on a given graph and (ii) basin complexity as a measure of complexity of partitions of the diversity space. We use these concepts to quantify chaoticity of computronsxe2x80x99 dynamics and the complexity of their basins of attraction. The theory is then extended into probabilistic machines where we define fuzzy basin partitioning of recurrent classes and introduce the concept of ergodic decomposition. A case study on 1D cyclic computron is provided with both deterministic and probabilistic versions.