# Exploring Kolmogorov Complexity Approximations for Data Analysis: Insights and Applications

Jorge Miguel Silva, Diogo Pratas, Sérgio Matos

► To cite this version:

Jorge Miguel Silva, Diogo Pratas, Sérgio Matos. Exploring Kolmogorov Complexity Approximations for Data Analysis: Insights and Applications. 14th Doctoral Conference on Computing, Electrical and Industrial Systems (DoCEIS), Jul 2023, Monte Da Caparica, Portugal. pp.161-174, 10.1007/978-3-031-36007-7_12. [https://inria.hal.science/hal-05473091v1](https://inria.hal.science/hal-05473091v1)

HAL Id: hal-05473091

Submitted on 23 Jan 2026

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Exploring Kolmogorov Complexity Approximations for Data Analysis: Insights and Applications

Jorge Miguel Silva<fnref n="1" />(✉), Diogo Pratas<fnref n="1" />,<fnref n="2" />,<fnref n="3" />(✉), and Sérgio Matos<fnref n="1" />,<fnref n="2" />(✉)

**Abstract.** This paper presents a PhD research project focused on investigating the use of Kolmogorov complexity approximations as descriptors for various data types, with the aim of addressing inversion problems. The research explores the application of these approximations across different domains while considering the relationship between algorithmic and probabilistic complexities. The study starts with genomic data analysis, where specialized data compressors are employed to improve taxonomic identification, classification, and organization. The research then extends to analysing artistic paintings, utilizing information-based measures to attribute authorship, categorize styles, and describe the content. Additionally, the research examines Turing Machine-generated data, providing insights into the relationship between algorithmic and probabilistic complexities. A method for increasing probabilistic complexity without affecting algorithmic complexity is also proposed. Lastly, a methodology for identifying programs capable of generating outputs approximating given input strings is introduced, offering potential solutions to inversion problems. The paper highlights this research's diverse applications and findings, contributing to understanding the relationship between algorithmic and probabilistic complexities in data analysis.

**Keywords:** Algorithmic-Statistical Information · Kolmogorov Complexity · Data Compression

## 1 Introduction

The rapid growth of data and computational power in recent years has led to an increased focus on understanding the interplay between computation and information. This has fueled significant advancements in Algorithmic Information Theory (AIT), which investigates the properties of algorithms and their relationship with the information content of their inputs and outputs [1]. AIT is a field of study that explores the measurement of an object's complexity in terms of the minimum number of bits required for a program to compute it and halt without loss of information.

<footnote n="1">¹ IEETA, Institute of Electronics and Informatics Engineering of Aveiro and LASI, Intelligent Systems Associate Laboratory, University of Aveiro, Aveiro, Portugal
jorge.miguel.ferreira.silva@ua.pt</footnote>

<footnote n="2">² DETI, Department of Electronics, Telecommunications and Informatics, University of Aveiro, Aveiro, Portugal</footnote>

<footnote n="3">³ DoV, Department of Virology, University of Helsinki, Helsinki, Finland</footnote>
The potential applications of AIT span many fields, including bioinformatics [2], data compression [3], machine learning [4, 5], cryptography [6, 7], and even art [8]. In bioinformatics, AIT facilitates the analysis of genomic sequences [9], aiding in tasks such as identifying conserved regions [10], uncovering functional elements [11], and understanding evolutionary processes [12].

For data compression, AIT plays a crucial role in informing the development of more efficient compression algorithms through algorithmic modelling. By modeling the algorithmic structure of data, AIT-based methods can achieve superior compression rates by capturing the inherent patterns and redundancies in various data types, such as text, images, video, and audio streams.

In machine learning, AIT can potentially enhance model interpretability and performance by providing more concise representations of the learned patterns [13, 14]. This can lead to better generalization, reduce overfitting, and improve the understanding of the underlying mechanisms driving the data. Furthermore, AIT-inspired techniques can be employed for feature selection, model comparison, and complexity regularization, ensuring more robust and efficient learning processes [15].

AIT has also found applications in cryptography, where it has been used to analyze the randomness and security of cryptographic primitives [16, 17]. By quantifying the information content of keys and ciphertexts, AIT can help assess the strength of encryption schemes and guide the development of more secure protocols [18].

AIT has been employed in art to analyze and classify artistic styles, offering an objective and quantitative approach to understanding the creative process. By examining the complexity of artistic elements, researchers have been able to identify patterns, trace influences, and uncover the evolution of styles over time. This has opened up new avenues for interdisciplinary research at the intersection of art, computation, and information theory [8].

The primary motivation for this work was to investigate the usage of Kolmogorov Complexity approximations, particularly its usage in 1d and 2d digital objects such as genomic sequences, images, and algorithmically generated sequences, advancing knowledge in these areas, as well as investigate how these approximations can be used to solve the inversion problem. Therefore, our exploration's central research question was: "How can Kolmogorov complexity approximations be employed as descriptors of different data types and be used to solve inversion problems?".

This paper explores the use of approximations of Kolmogorov complexity as descriptors for a wide range of data types, including genomic sequences and artistic paintings. Our investigation led to the creation of new methodological advancements and provided fresh insights into these fields.

Afterwards, we investigate the relationship between probabilistic and algorithmic complexity using Turing Machines' tapes. Finally, we investigate how these methods can solve inversion problems through approximations.

The paper is organized as follows: Section II offers background information on Kolmogorov complexity and Algorithmic Information Theory, presenting their key concepts and mathematical foundations. Section III discusses AIT applications in genomics, providing a detailed account of its contributions to sequence analysis and viral classification. Section IV delves into the applications of AIT in art, exploring the use of Kolmogorov
complexity to analyze and classify artistic styles and the detection of artists' influencing relationships. Section V investigates the relationship between probabilistic and algorithmic complexity and how this relationship can be used to approximate a possible solution to the inversion problem.

Finally, section VI summarises our findings and concludes with a discussion of future research directions in AIT, highlighting emerging trends and open questions that emerged at the end of the doctorate.

## 2 Kolmogorov Complexity, Algorithmic Information Theory, and Applications

Kolmogorov complexity, a fundamental concept in computer science and information theory, provides a means of quantifying the information content of an object [19]. The complexity is defined as the length of a shortest program capable of generating the object, typically using a fixed reference universal Turing machine [9]. By capturing the size of the most concise description of an object, Kolmogorov complexity inherently considers the structure and regularities within the object [20].

Algorithmic Information Theory delves into the interplay between computation and information [21]. It integrates Kolmogorov complexity with Shannon's information theory to establish a mathematical framework for evaluating the information content of individual objects. While Shannon's information theory concerns the average information content of message ensembles, AIT focuses on the intrinsic algorithmic properties of specific objects, providing a deeper understanding of their structure and complexity [9, 20].

Data compression, one of the primary applications of Kolmogorov complexity and AIT relies on the principle that a more compact program describing an object enables compression into a smaller size without any loss of information [9]. Lossless data compression, in particular, seeks to minimize data size while preserving the ability to reconstruct the original data perfectly [22]. By leveraging the structure and regularities within the data, AIT-based compression methods can achieve high compression rates for various data types, including text [23], images [24], and genomic sequences [3].

In addition to data compression, Kolmogorov complexity and AIT find applications in several domains, including data analysis, pattern recognition, feature selection, model comparison, and anomaly detection [9]. These applications benefit from the insights of measuring an object's Kolmogorov complexity, which can reveal information about its inherent structure and patterns. For instance, identifying high or low-complexity regions within a dataset can help detect distinct patterns or features, which may be helpful in tasks such as sequence alignment, classification, or clustering [25–27].

Furthermore, AIT-based methods can facilitate the comparison of models or algorithms, providing a robust means of assessing their performance and complexity [13]. In machine learning, for example, AIT can be applied to model selection, guiding the choice of an optimal model based on the trade-off between complexity and fitting of the data [28]. In the context of algorithm analysis, AIT can study algorithms' efficiency and resource requirements, offering insights into their time and space complexity [29].
In recent years, AIT has been increasingly used to address challenges in diverse fields, such as genomics [30], neuroscience [31], and art classification [8]. This paper provides a comprehensive overview of Kolmogorov complexity, Algorithmic Information Theory, and their diverse applications. By delving into the theoretical foundations and practical use cases, we aim to highlight the potential of AIT to advance our understanding of the information content and structure inherent in a wide range of data types, ultimately contributing to developing novel methods and techniques across various domains.

# 3 Genomic Sequence Analysis Using Kolmogorov Complexity Approximations

This section explores the application of Kolmogorov complexity approximations in genomic sequence analysis. The primary goals include developing novel computational methods for analyzing and classifying viral genomes, identifying unique features in viral sequences, and contributing to a better understanding of the relationships between different viral families and genera. The work was validated in the following articles [26, 30, 32]. Furthermore, we also contributed with the following open-source repositories [33–35] as well as a web-page [36].

## 3.1 Methodology

The methodology employed in this research centers on efficiently approximating the Kolmogorov complexity with data compression algorithms, specifically GeCo3, to analyze natural genomic sequences. The Normalized Compression (NC) was used to approximate the Kolmogorov complexity of genomic sequences, mathematically described as follows:

$$NC(x) = \frac{C(x)}{|x|\log_2|\theta|} \qquad (1)$$

where x is the string, C(x) represents the number of bits needed by the lossless data compression program to represent the string x, |θ| is the size of the alphabet and |x| is the length of the string x.

The lower the value of NC, the higher the sequence's redundancy (or lower complexity).

To evaluate the effectiveness of GeCo3 in quantifying regions described by simple algorithmic sources, it was benchmarked against other high compression ratio general-purpose data compressors (PAQ and cmix) and a measure that combines small algorithmic programs and Shannon entropy (Block Decomposition Method or BDM). The analysis revealed that GeCo3 could efficiently address and quantify regions properly described by simple algorithmic sources, such as inverted repeats (exact and approximate), among other characteristics. GeCo3 was used with three different configurations to detect inverted repeats (IRs) and quantify their abundance in each genome:

A configuration with a specific module to detect IRs (GeCo3-IR). A configuration without the module to detect IRs (GeCo3-noIR). A configuration that used both modules during compression (GeCo3-both). By comparing the NC values computed using each
configuration, the abundance of IRs in each genome was quantified. The detection of IRs was fundamental to the research, as it served as an essential criterion for characterizing the genomic sequences.

The main objectives of this research were to develop a method for taxonomic classification using compression-based measures by approximating the Kolmogorov complexity of genomic sequences and comparing them to a reference database of known sequences, identify the structural description of the viral genome using minimal bi-directional complexity profiles to visualize the distribution of complexity locally and describe structural regions detected in the genome with other methods, and analyze rich genomic features to correctly identify viruses and archaea's taxon by examining the frequency of occurrence of specific motifs or patterns in genomes.

## 3.2 Viral Complexity Landscape

Our study aimed to explore the diversity of viruses in terms of genome size, structure, and content while addressing the limitations of traditional virus classification methods that often rely on phenotypic characteristics. To achieve this, we employed efficient approximations of the Kolmogorov complexity to analyze the complexity landscape of viral genomes and elucidate the relationships between different viral families and genera from a computational perspective.

Our findings revealed that, on average, dsDNA viruses are the most redundant (least complex) according to their size. This result is consistent with that dsDNA viruses typically have larger genomes. Conversely, we found that ssDNA viruses are the least redundant, indicating that they have more complex genomes despite their smaller sizes. Interestingly, we also discovered that dsRNA viruses show lower redundancy than ssRNA viruses, an intriguing finding considering the RNA viruses' rapid evolution and adaptation capabilities.

By examining the complexity landscape according to genome type, our study highlights the differences between various viral groups, such as dsDNA, ssDNA, dsRNA, and ssRNA viruses. The results demonstrate that smaller genomes, such as ssDNA and dsRNA, tend to have higher complexity, while larger genomes, such as dsDNA, are less complex. These findings are consistent with the inverse correlation observed between genome size and normalized compression (NC), a measure used to compare the proportions of the absence of redundancy independently from the sizes of the genomes.

Furthermore, we analyzed the complexity landscape according to taxonomic levels, such as Realm, Kingdom, Phylum, Class, Order, Family, and Genus. This approach allowed us to observe patterns and associations among viral taxa and understand the role of inverted repeats (IRs) in viral genomes. We found that certain viral families, such as Adnaviria, Varidnaviria, and Duplodnaviria, have low complexity due to their larger genome sizes and dsDNA nature. However, within these groups, some realms, like Adnaviria, exhibit higher complexity, suggesting that they are more complex than other dsDNA viruses.

Additionally, we explored the complexity landscape of specific viral families, such as Herpesviridae. Our results revealed a significant variation between the genera in this family, with some exhibiting high levels of inverted repeats (IRs). In contrast, others showed very low compression with the IR detection subprogram. We postulate that
these variations in complexity could be related to different rates of evolution within
these genomes.

**3.3 Classification Performance and Impact of Normalized Compression**

In this study, we examined the classification performance of our feature-based method, focusing on the impact of normalized compression (NC) as a genomic descriptor, which approximates Kolmogorov complexity. The primary goal was to determine if NC and Kolmogorov complexity approximations are effective data descriptors for classifying viral and archaea genomes.

Our results demonstrate that the NC feature significantly contributes to the clas-
sification performance. When used alone, the NC achieves relatively high accuracy
and F1-score compared to the other individual features, indicating that the information
derived from NC effectively captures essential genomic characteristics.

In our experiments, we observed that the accuracy and F1-score of the XGBoost
classifier improved substantially when combining all features (NC, GC-content, and
sequence length) compared to using only the NC feature. This improvement is observed
across different taxonomic classification tasks in viral and archaea domains. This finding
suggests that the NC feature, as an approximation of Kolmogorov complexity, is a robust
data descriptor that can be employed in genomic sequence classification.

Furthermore, combining NC with other features, such as GC content and sequence length (SL), further enhances the classification performance. This improvement demonstrates a synergistic effect between these features, capturing complementary information that enhances the classification process.

**3.4 Insights**

This section delved into applying Kolmogorov complexity approximations in genomic sequence analysis.

We found that Kolmogorov complexity approximations, specifically normalized
compression (NC), are suitable for analysing and classifying viral genomes. The devel-
oped classification method's effectiveness in classifying viral and archaea genomes at
various taxonomic levels demonstrates the potential of leveraging Kolmogorov com-
plexity approximations for genomic classification tasks. Furthermore, we observed a
synergistic effect achieved by combining NC with other genomic features, such as GC
content and sequence length. This significantly improved the classification performance,
suggesting that incorporating multiple complementary features can lead to more accu-
rate and reliable classification outcomes. These insights showcase the potential of using
Kolmogorov complexity approximations for genomic sequence analysis, particularly
for classifying viral genomes. The results contribute to the ongoing advancement of
genomic analysis techniques and provide a foundation for developing more accurate,
comprehensive, and robust classification methods in the future.
# 4 2D Data Analysis Using Kolmogorov Complexity Approximations

This section focused on applying Kolmogorov complexity approximations to 2D data analysis, specifically for artistic paintings. We present our findings by comparing complexity measures, their application in artistic paintings, and the potential improvements to existing classification methodologies. The work was validated in [27]. Furthermore, we also contributed with the following open-source repositories [37] as well as a web-page [38].

## 4.1 Comparison of Complexity Measures

Our analysis began with comparing Normalized Compression (NC), and Block Decomposition Method (BDM) measures to understand their respective strengths and weaknesses in measuring image complexity. We conducted experiments on different types of images, including cellular automata, X-ray images, paintings, and others, to assess the performance of each measure under various conditions. BDM was found to help identify data content similar to simple algorithms but had difficulty dealing with uniform pixel edition and lossless information quantification due to block representability. This limitation affected its performance when applied to highly uniformed images or where information was distributed unevenly. Conversely, NC was more robust to data alterations, such as pixel edition and quantization, and was better suitable for measuring the quantity of information in artistic paintings without underestimating it. This robustness made NC more suitable for a broader range of image types, including those with varying degrees of complexity and uniformity.

## 4.2 Applications of Complexity Measures in Artistic Paintings

Using these complexity measures, we investigated their application in the context of artistic paintings. We assessed the potential of NC as a stylistic descriptor by combining it with the roughness exponent $\alpha$. This combination effectively identified hidden patterns and relationships in paintings with the same complexity range, providing valuable insights into the similarities and differences between various art styles.

In addition to using NC as a stylistic descriptor, we explored the concept of complexity fingerprints to explain art content and aid art authorship attribution and validation. By examining how each artist typically distributes content on canvas, we could discern unique patterns that enabled to differentiate between artists and validate their authorship.

## 4.3 Revealing Relationships Between Artists Using Complexity Measures

Moreover, our study discovered interesting links between artists based on the distance between their regional complexity. This approach highlighted shared techniques and stylistic influences, suggesting that complexity measures can be used to relate artists and provide insights into their stylistic connections and potential influences on each other's work. The relationships revealed by these complexity measures could be valuable for art historians and researchers studying the evolution of art styles and the impact of individual artists on their contemporaries.
## 4.4 Improving Classifications Methodologies with Regional Complexity and HDC Function

Lastly, we examined whether the regional complexity and the Height Difference Cor-
relation (HDC) function of paintings could be used as additional features to improve
existing author and style classification methodologies. To test this hypothesis, we inte-
grated these features into a classification pipeline and evaluated their performance on a
dataset of artistic paintings.

Our results showed that incorporating regional complexity and HDC features led
to a significant increase in classification accuracy, indicating that these measures can
effectively extract information that differs from non-handcrafted features. This finding
supports the potential of complexity measures to improve current methodologies in
classifying artistic paintings and emphasizes the relevance of regional complexity as a
descriptor of images in this context.

## 4.5 Summary

In summary, our exploration of 2D data analysis using Kolmogorov complexity approx-
imations in the field of artistic paintings has led to several noteworthy findings. We
demonstrated the strengths and weaknesses of NC and BDM measures in measuring
image complexity and assessed their sensitivity to data alterations. Furthermore, we
showed that the combination of NC and the roughness exponent α could be an ade-
quate stylistic descriptor and that complexity fingerprints can be valuable for art content
explanation, authorship attribution, and validation. Additionally, our study highlighted
the potential of complexity measures to reveal relationships between artists based on
shared techniques and stylistic influences.

Finally, we provided evidence that was incorporating regional complexity and HDC
function as additional features can improve existing classification methodologies for
artistic paintings. These findings aid in the development of computer-based analysis
techniques for art and open new avenues for future research in this field.

# 5 Evolving Probabilistic Complexity in Turing Machines

In this section, we explore the evolution of probabilistic complexity in Turing Machine (TM) tapes, maintaining the same level of algorithmic complexity. We demonstrate its potential applications by devising a methodology to increase probabilistic complexity. The content of this section is validated in [39]. Additionally, we discuss a new approach to approximate the inverse problem in Turing machines, comparing different search strategies and addressing the challenges and limitations in this context. For this section we also contributed with the following open-source repositories [40–43].

## 5.1 Analyzing Probabilistic Complexity in TM Tapes

Our investigation began by analyzing TMs with low algorithmic complexity, i.e., a
small number of states and alphabet. Then, we employed a compression-based measure,
approximated by the best-order Markov model, to quantify the probabilistic complexity of the generated tapes. By examining the compression-based approach concerning symbol editions and block transformations, we identified two distinct regions with higher Normalized Compression (NC) patterns in the tapes produced by TMs with the same number of states and alphabet. These regions were associated with repetitive short cycles in the configuration matrix, resulting from sequential modifications in the matrix and leading to shorter tapes.

## 5.2 Complexity Profiles

We introduced normal and dynamic complexity profiles as approximate measures to quantify local complexity. Normal complexity profiles allow us to localize higher and lower probabilistic complexity areas in machines that reached the external halting condition. In contrast, dynamic complexity profiles enable us to track the temporal dynamics of probabilistic complexity through the tape's modification cycles. By applying both profiles, we could draw meaningful insights regarding global quantities.

We also compared a measure incorporating algorithmic and probabilistic approaches (Block Decomposition Method or BDM) to analyze the tapes. Although BDM was found to be an efficient describer of the tapes generated by TMs with specific conditions, for a higher number of states, our methodology progressively approximated the BDM.

## 5.3 Increasing Probabilistic Complexity

We developed an algorithm capable of progressively increasing a tape's probabilistic complexity. This algorithm generates a tape that evolves through a stochastic optimization rule matrix, modified according to the quantification of the NC. Consequently, this algorithm can be adapted to vary the value of the NC. By implementing and comparing two methods to increase probabilistic complexity, we found that the second method was more effective at systematically increasing the probabilistic complexity of TMs while retaining algorithmic complexity.

## 5.4 Potential Applications and Implications

Our algorithm for increasing probabilistic complexity while maintaining algorithmic complexity has several potential applications in bioinformatics. For instance, the output of these TMs can be used as input to test and quantify the accuracy of genome assembly algorithms for different complexities from nonstationary sources. Another application involves simulating progressive mutations in metagenomic communities or complementing absent regions of genome viruses due to sequencing limitations or DNA/RNA degradation. A broader application includes benchmarking compression algorithms used to localize complexity in the data, considering possible algorithmic sources. These applications demonstrate the significance of our findings in understanding and manipulating probabilistic complexity in Turing Machines.
## 5.5 Approximating the Inverse Problem in Turing Machines

Building upon our exploration of probabilistic complexity in TM tapes, we introduce a methodology to approximate the inverse problem in Turing machines, which aims to find programs capable of generating given strings. By defining a search space with the specific alphabet and state cardinalities, we focus on candidate programs more likely to produce the target string.

We generate candidate Turing machines within the search space and simulate their execution for a predetermined number of iterations. Upon halting, we compare the output strings to the target string using a loss function based on the Kullback-Leibler divergence, which measures the dissimilarity between probability distributions.

We employ a Guided search approach inspired by the A* search algorithm to navigate the vast search space efficiently. This heuristic-driven method prioritizes candidate programs more likely to produce the target string and iteratively refines the search parameters and the number of iterations for enhanced approximation.

Our methodology for addressing the inverse problem in Turing machines connects with the complexity profiles and the algorithm for increasing probabilistic complexity. It provides a framework to discover programs that generate strings with desired complexity properties. By combining loss function minimization, Guided search, and an iterative search strategy, we present a comprehensive approach to identify Turing machines that best represent given strings.

## 5.6 Comparing Search Strategies

To evaluate the effectiveness of our methodology, we compared three search strategies for finding candidate programs that represent the strings: sequential search, Monte Carlo search, and Guided search. Sequential search explores the search space systematically, Monte Carlo search employs random sampling, and Guided search uses heuristics to prioritize promising candidates.

Our comparison results demonstrated that Guided search consistently outperformed the other two methods regarding minimal average loss and the number of found solutions. This finding highlights the potential advantage of Guided search in approximating the inverse problem in Turing machines, suggesting that incorporating heuristic information can significantly improve the search process.

## 5.7 Challenges and Limitations

Despite the promising results, our methodology faced some challenges and limitations. The vastness of the search space required a time-constrained evaluation method, which limited the search for small tapes. As a result, the compression suffered in many cases, as more bits were required to represent the program than those needed to represent the target string.

Additionally, our methodology's performance was tested only on synthetically generated data, which may not accurately represent the complexity of real-world data. Therefore, further research and testing are needed to address these challenges, refine the
methodology for broader applications, and validate its effectiveness in more complex
and noisy data.

These new findings, combined with our existing work on evolving probabilistic com-
plexity in Turing machines, contribute to our understanding of the relationship between
algorithmic and probabilistic complexity and offer potential applications in bioinfor-
matics, compression algorithms, and other fields where data complexity plays a crucial
role.

5.8 Conclusions and Future Work

This doctorate explores the use of Kolmogorov complexity approximations for data description and classification. We apply it to various data types, such as 1D genomic sequences, 2D paintings, and algorithmic data. Our findings demonstrate the importance and versatility of these approximations in improving classification results for artistic paintings, taxonomic identification, and author and style attribution. We also provide insights into the redundancy of viral genomes and the complexity spectrum of paintings. Limitations and future directions include improving block representability, exploring other data types, and refining compression-based measures to better detect programs and improve classifications. Overall, this study lays a strong foundation for future applications of Kolmogorov complexity approximations in diverse domains.

6 Relationship to Connected Cyber-Physical Spaces

Our research on Kolmogorov complexity approximations explores potential advance-
ments in data analysis for interconnected systems found in connected cyber-physical
spaces. These spaces require efficient data management and analysis for optimal per-
formance and reliability, as they integrate computational and physical processes for
seamless communication, data exchange, and real-time analytics.

Though our study focuses on genomic data and artistic paintings, the underlying
concepts and techniques could apply to other domains within cyber-physical spaces.
Additionally, our research emphasizes the development of specialized data compres-
sors, which could enhance efficient data storage and transmission, a crucial aspect for
maintaining high-speed communication in interconnected systems.

Our proposed methodology for solving inversion problems aims to identify programs that generate outputs similar to given input strings. This approach can be used to tackle challenges such as reconstructing original data from compressed or noisy versions, which could have implications in various domains within Connected Cyber-Physical Spaces, including error detection and correction in communication systems.

In conclusion, our research on Kolmogorov complexity approximations con-
tributes to developing innovative data representation, compression, and problem-solving
approaches, potentially supporting more efficient, reliable, and secure interconnected
systems within the cyber-physical domain.

**Acknowledgments.** This work was partially funded by National Funds through the FCT - Founda-
tion for Science and Technology, in the context of the project UIDB/00127/2020. Furthermore, this
work has received funding from the EC under grant agreement 101081813, Genomic Data Infras-
tructure. J.M.S. acknowledges the FCT grant SFRH/BD/141851/2018. National funds funded D.P.
through FCT – Fundação para a Ciência e a Tecnologia, I.P., under the Scientific Employment
Stimulus - Institutional Call - reference CEECINST/00026/2018.

References

1. Hutter, M.: Algorithmic information theory. Scholarpedia 2, 2519 (2007)

2. Nalbantoglu, Ö., Russell, D., Sayood, K.: Data compression concepts and algorithms and their applications to bioinformatics. Entropy **12**(1), 34–52 (2009). https://doi.org/10.3390/e12010034

3. Silva, M., Pratas, D., Pinho, A.J.: Efficient DNA sequence compression with neural networks. GigaScience **9**(11), giaa119 (2020). https://doi.org/10.1093/gigascience/giaa119

4. MacKay, D.J.C., Mac Kay, D.J.C.: Information theory, inference and learning algorithms. Cambridge University Press, Cambridge (2003)

5. Cohen, A.R., Bjornsson, C.S., Temple, S., Banker, G., Roysam, B.: Automatic summarization of changes in biological image sequences using algorithmic information theory. IEEE Trans. Pattern Anal. Mach. Intell. **31**(8), 1386–1403 (2009). https://doi.org/10.1109/TPAMI.2008.162

6. Maurer, U.: Information-theoretic cryptography. In: Wiener, M. (ed.) Advances in Cryptology — CRYPTO' 99. LNCS, vol. 1666, pp. 47–65. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_4

7. Yeboah-Ofori, A., Agbodza, C.K., Opoku-Boateng, F.A., Darvishi, I., Sbai, F.: Applied cryptography in network systems security for cyberattack prevention. In: 2021 International Conference on Cyber Security and Internet of Things (ICSIoT), pp. 43–48 (2021)

8. Tenreiro Machado, J., Lopes, A.M.: Artistic painting: a fractional calculus perspective. Appl. Math. Model. **65**, 614–626 (2019)

9. Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and its Applications. TCS, Springer, New York (2008). https://doi.org/10.1007/978-0-387-49820-1

10. Voss, R.F.: Evolution of long-range fractal correlations and 1/f noise in DNA base sequences. Phys. Rev. Lett. **68**(25), 3805–3808 (1992). https://doi.org/10.1103/PhysRevLett.68.3805

11. Ciliberti, S., Martin, O.C., Wagner, A.: Innovation and robustness in complex regulatory gene networks. Proc. Natl. Acad. Sci. **104**(34), 13591–13596 (2007). https://doi.org/10.1073/pnas.0705396104

12. Adami, C., Ofria, C., Collier, T.C.: Evolution of biological complexity. Proc. Natl. Acad. Sci. **97**(9), 4463–4468 (2000). https://doi.org/10.1073/pnas.97.9.4463

13. Rissanen, J.: Modeling by shortest data description. Automatica **14**(5), 465–471 (1978)

14. RossQuinlan, J., Rivest, R.L.: Inferring decision trees using the minimum description length principle. Inf. Comput. **80**(3), 227–248 (1989). https://doi.org/10.1016/0890-5401(89)90010-2

15. Davies, D.L., Bouldin, D.W.: A cluster separation measure. IEEE Trans. Pattern Anal. Mach. Intell. **PAMI-1**(2), 224–227 (1979). https://doi.org/10.1109/TPAMI.1979.4766909

16. Dodis, Y., Reyzin, L., Smith, A.: Fuzzy extractors: how to generate strong keys from bio-
metrics and other noisy data. In: Cachin, C., Camenisch, J.L. (eds.) Advances in Cryptology
- EUROCRYPT 2004. LNCS, vol. 3027, pp. 523–540. Springer, Heidelberg (2004). https://
doi.org/10.1007/978-3-540-24676-3_31

17. Chaitin, G.J.: Algorithmic information theory. IBM J. Res. Dev. **21**(4), 350–359 (1977)

18. Bruce, S.: Applied cryptography: Protocols, Algorithms, and Source Code in c.-2nd (1996)
19. Kolmogorov, A.N.: Three approaches to the quantitative definition of information. Probl. Inf. Trans. **1**(1), 1–7 (1965)

20. Chaitin, G.J.: On the length of programs for computing finite binary sequences: statistical considerations. J. ACM (JACM). **16**(1), 145–159 (1969)

21. Calude, C.S.: Information and Randomness: An Algorithmic Perspective. Springer Science & Business Media, Heidelberg (2002). https://doi.org/10.1007/978-3-662-03049-3

22. Sayood, K.: Introduction. In: Introduction to data compression, pp. 1–10. Elsevier (2018). https://doi.org/10.1016/B978-0-12-809474-7.00001-X

23. Moffat, A.: Word-based text compression. Softw. Pract. Exp. **19**(2), 185–198 (1989). https://doi.org/10.1002/spe.4380190207

24. Knoll, B., de Freitas, N.: A machine learning perspective on predictive coding with PAQ8. In: 2012 Data Compression Conference, pp. 377–386. IEEE (2012)

25. Carrasco, R.C., Oncina, J.: Learning stochastic regular grammars by means of a state merging method. In: Carrasco, R.C., Oncina, J. (eds.) Grammatical Inference and Applications. LNCS, vol. 862, pp. 139–152. Springer, Heidelberg (1994). https://doi.org/10.1007/3-540-58473-0_144

26. Silva, J.M., Pratas, D., Caetano, T., Matos, S.: The complexity landscape of viral genomes. GigaScience **11**, 1–16 (2022). https://doi.org/10.1093/gigascience/giac079

27. Silva, J.M., Pratas, D., Antunes, R., Matos, S., Pinho, A.J.: Automatic analysis of artistic paintings using information-based measures. Pattern Recogn. **114**, 107864 (2021). https://doi.org/10.1016/j.patcog.2021.107864

28. Wallace, C.S.: Minimum message length and kolmogorov complexity. Comput. J. **42**(4), 270–283 (1999). https://doi.org/10.1093/comjnl/42.4.270

29. Hutter, M.: Universal algorithmic intelligence: a mathematical top→down approach. In: Goertzel, B., Pennachin, C. (eds.) Artificial general intelligence, pp. 227–290. Springer Berlin Heidelberg, Heidelberg (2007). https://doi.org/10.1007/978-3-540-68677-4_8

30. Silva, J.M., Almeida, J.R.: The value of compression for taxonomic identification. In: 2022 IEEE 35th International Symposium on Computer-Based Medical Systems (CBMS), pp. 276–281. IEEE (2022)

31. Zenil, H., Delahaye, J.-P.: An algorithmic information theoretic approach to the behaviour of financial markets. J. Econ. Surv. **25**(3), 431–463 (2011)

32. Silva, J.M., Pratas, D., Caetano, T., Matos, S.: Feature-based classification of archaeal sequences using compression-based methods. In: Pinho, A.J., Georgieva, P., Teixeira, L.F., Sánchez, J.A. (eds.) Pattern Recognition and Image Analysis, pp. 309–320. Springer International Publishing, Cham (2022). https://doi.org/10.1007/978-3-031-04881-4_25

33. jorgeMFS. Complexity Analysis VirAl Sequences (C.A.N.V.A.S.) Repository (2021). https://github.com/jorgeMFS/canvas

34. jorgeMFS. Classification and identification of Archaea (ARCHAEA2) Repository (2021). https://github.com/jorgeMFS/Archaea2

35. bioinformatics ua. COMPressor tAxonomic Classification (C.O.M.P.A.C.T.) Repository (2021). https://github.com/bioinformatics-ua/COMPACT

36. CANVAS Website. CANVAS Website (2021). https://asilab.github.io/canvas/

37. asilab. Measuring probabilistic-algorithmic information of artistic paintings (PANTHER) Repository (2021). https://github.com/asilab/panther

38. PANTHER Website. PANTHER Website (2021). http://panther.web.ua.pt/

39. Silva, J.M., Pinho, E., Matos, S., Pratas, D.: Statistical complexity analysis of turing machine tapes with fixed algorithmic complexity using the best-order Markov model. Entropy. **22**(1), 105 (2020)

40. asilab. TMCompression Repository (2021). https://github.com/asilab/TMCompression

41. jorgeMFS.Turing Machine Recreator (TMRecreator) (2021). https://github.com/jorgeMFS/TMRecreator
42. jorgeMFS. SPTTM (2021). https://github.com/jorgeMFS/spttm

43. bioinformatics ua. TM Neural Finder (2021). https://github.com/bioinformatics-ua/TM-Neural-Finder