Publications (116)
Algorithmic Complexity and Reprogrammability of Chemical Structure Networks
Hector Zenil, Narsis A. Kiani, Ming-Mei Shang +1
Here we address the challenge of profiling causal properties and tracking the transformation of chemical compounds from an algorithmic perspective. We explore the potential of appl…
Similarity Analysis of Blood Count Reference Intervals Across Continents Reveals No Reproducible Population or Geography-Linked Structure and Supports Personalised Values
Kunlin Wu, Abicumaran Uthamacumaran, Hector Zenil
Blood reference intervals (RIs) underpin diagnostic interpretation and therapeutic monitoring worldwide. However, many widely used RI systems originate from limited historical coho…
Predictive Systems Toxicology
Narsis A. Kiani, Ming-Mei Shang, Hector Zenil +1
In this review we address to what extent computational techniques can augment our ability to predict toxicity. The first section provides a brief history of empirical observations…
Low Algorithmic Complexity Entropy-deceiving Graphs
Hector Zenil, Narsis Kiani, Jesper Tegnér
In estimating the complexity of objects, in particular of graphs, it is common practice to rely on graph- and information-theoretic measures. Here, using integer sequences with pro…
Undecidability and Irreducibility Conditions for Open-Ended Evolution and Emergence
Santiago Hernández-Orozco, Francisco Hernández-Quiroz, Hector Zenil
Is undecidability a requirement for open-ended evolution (OEE)? Using methods derived from algorithmic complexity theory, we propose robust computational definitions of open-ended…
Algorithmic complexity for psychology: A user-friendly implementation of the coding theorem method
Nicolas Gauvrit, Henrik Singmann, Fernando Soler-Toscano +1
Kolmogorov-Chaitin complexity has long been believed to be impossible to approximate when it comes to short sequences (e.g. of length 5-50). However, with the newly developed \emph…
A Simplicity Bubble Problem in Formal-Theoretic Learning Systems
Felipe S. Abrahão, Hector Zenil, Fabio Porto +3
When mining large datasets in order to predict new data, limitations of the principles behind statistical machine learning pose a serious challenge not only to the Big Data deluge,…
Leveraging Pre-Trained Neural Networks to Enhance Machine Learning with Variational Quantum Circuits
Jun Qi, Chao-Han Yang, Samuel Yen-Chi Chen +3
Quantum Machine Learning (QML) offers tremendous potential but is currently limited by the availability of qubits. We introduce an innovative approach that utilizes pre-trained neu…
Algorithmic Causal Deconvolution of Intertwined Programs and Networks by Generative Mechanism
Hector Zenil, Narsis A. Kiani, Allan A. Zea +1
Complex data usually results from the interaction of objects produced by different generating mechanisms. Here we introduce a universal, unsupervised and parameter-free model-orien…
On the Complexity and Behaviour of Cryptocurrencies Compared to Other Markets
Daniel Wilson-Nunn, Hector Zenil
We show that the behaviour of Bitcoin has interesting similarities to stock and precious metal markets, such as gold and silver. We report that whilst Litecoin, the second largest…
Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures
Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye +1
We show that real-value approximations of Kolmogorov-Chaitin (K_m) using the algorithmic Coding theorem as calculated from the output frequency of a large set of small deterministi…
On complexity of post-processing in analyzing GATE-driven X-ray spectrum
Neda Gholami, Mohammad Mahdi Dehshibi, Mahmood Fazlali +3
Computed Tomography (CT) imaging is one of the most influential diagnostic methods. In clinical reconstruction, an effective energy is used instead of total X-ray spectrum. This ap…
An Algorithmic Approach to Information and Meaning
Hector Zenil
I will survey some matters of relevance to a philosophical discussion of information, taking into account developments in algorithmic information theory (AIT). I will propose that…
Controllability, Multiplexing, and Transfer Learning in Networks using Evolutionary Learning
Rise Ooi, Chao-Han Huck Yang, Pin-Yu Chen +5
Networks are fundamental building blocks for representing data, and computations. Remarkable progress in learning in structurally defined (shallow or deep) networks has recently be…
Algorithmic Complexity for Short Binary Strings Applied to Psychology: A Primer
Nicolas Gauvrit, Hector Zenil, Jean-Paul Delahaye +1
Since human randomness production has been studied and widely used to assess executive functions (especially inhibition), many measures have been suggested to assess the degree to…
Systematic Reconstruction of Disease Networks from Longitudinal Blood Data for Causal Discovery and Intervention Analysis
David Patrick Duys Montealegre, Alexander Fulton, Mahta Haghighat Ghahfarokhi +2
We explore the hyperparameters and introduce a methodological framework to convert disease patterns from time series data of blood test results into correlation graphs for causal h…
Computer Runtimes and the Length of Proofs: On an Algorithmic Probabilistic Application to Waiting Times in Automatic Theorem Proving
Hector Zenil
This paper is an experimental exploration of the relationship between the runtimes of Turing machines and the length of proofs in formal axiomatic systems. We compare the number of…
On the Dynamic Qualitative Behaviour of Universal Computation
Hector Zenil
We explore the possible connections between the dynamic behaviour of a system and Turing universality in terms of the system's ability to (effectively) transmit and manipulate info…
Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines
Fernando Soler-Toscano, Hector Zenil, Jean-Paul Delahaye +1
Drawing on various notions from theoretical computer science, we present a novel numerical approach, motivated by the notion of algorithmic probability, to the problem of approxima…
An algorithmic information-theoretic approach to the behaviour of financial markets
Hector Zenil, Jean-Paul Delahaye
Using frequency distributions of daily closing price time series of several financial market indexes, we investigate whether the bias away from an equiprobable sequence distributio…
Exploring Programmable Self-Assembly in Non-DNA based Molecular Computing
German Terrazas, Hector Zenil, Natalio Krasnogor
Self-assembly is a phenomenon observed in nature at all scales where autonomous entities build complex structures, without external influences nor centralised master plan. Modellin…
Multi-omic Enriched Blood-Derived Digital Signatures Reveal Mechanistic and Confounding Disease Clusters for Differential Diagnosis
Bolin Liu, Abicumaran Uthamacumaran, Alexander Fulton +1
Understanding disease relationships through blood biomarkers offers a pathway toward data-driven taxonomy and precision medicine. In this study, we constructed a digital blood twin…
Asymptotic Behaviour and Ratios of Complexity in Cellular Automata
Hector Zenil
We study the asymptotic behaviour of symbolic computing systems, notably one-dimensional cellular automata (CA), in order to ascertain whether and at what rate the number of comple…
Towards a stable definition of Kolmogorov-Chaitin complexity
Jean-Paul Delahaye, Hector Zenil
Although information content is invariant up to an additive constant, the range of possible additive constants applicable to programming languages is so large that in practice it p…
Exhaustive Investigation of CBC-Derived Biomarker Ratios for Clinical Outcome Prediction: The RDW-to-MCHC Ratio as a Novel Mortality Predictor in Critical Care
Dmytro Leontiev, Abicumaran Uthamacumaran, Riya Nagar +1
Ratios of common biomarkers and blood analytes are well established for early detection and predictive purposes. Early risk stratification in critical care is often limited by the…
HiDi: An efficient reverse engineering schema for large scale dynamic regulatory network reconstruction using adaptive differentiation
Yue Deng, Hector Zenil, Jesper Tégner +1
The use of differential equations (ODE) is one of the most promising approaches to network inference. The success of ODE-based approaches has, however, been limited, due to the dif…
Empirical Encounters with Computational Irreducibility and Unpredictability
Hector Zenil, Fernando Soler-Toscano, Joost J. Joosten
There are several forms of irreducibility in computing systems, ranging from undecidability to intractability to nonlinearity. This paper is an exploration of the conceptual issues…
The Information-theoretic and Algorithmic Approach to Human, Animal and Artificial Cognition
Nicolas Gauvrit, Hector Zenil, Jesper Tegnér
We survey concepts at the frontier of research connecting artificial, animal and human cognition to computation and information processing---from the Turing test to Searle's Chines…
Très courte enquête sur l'extension non-triviale de la logique de propositions à la logique du premier et deuxième ordre
Hector Zenil
The formal construction of the second-order logic or predicate calculus essentially adds quantifiers to propositional logic. Why second-order logic cannot be reduced to that of the…
XGBoost-Powered Digital Twins Leverage Routine Blood Tests for Early Detection of Cancer and Cardiovascular Disease
Lo Kai Shun John, Riya Nagar, Abicumaran Uthamacumaran +1
Early detection of cancer and cardiovascular diseases is fundamental to improving patient outcomes and reducing healthcare expenditure. Current cancer screening programs are target…
Natural scene statistics mediate the perception of image complexity
Nicolas Gauvrit, Fernando Soler-Toscano, Hector Zenil
Humans are sensitive to complexity and regularity in patterns. The subjective perception of pattern complexity is correlated to algorithmic (Kolmogorov-Chaitin) complexity as defin…
Complejidad descriptiva y computacional en maquinas de Turing pequenas
Joost J. Joosten, Fernando Soler-Toscano, Hector Zenil
We start by an introduction to the basic concepts of computability theory and the introduction of the concept of Turing machine and computation universality. Then se turn to the ex…
Turing Patterns with Turing Machines: Emergence and Low-level Structure Formation
Hector Zenil
Despite having advanced a reaction-diffusion model of ODE's in his 1952 paper on morphogenesis, reflecting his interest in mathematical biology, Alan Turing has never been consider…
Complexity-Informed Causal Modeling of Neurodevelopmental Trajectories in Pediatric High-Grade Gliomas: Divergences from Neural Stem Cell Signatures
Abicumaran Uthamacumaran, Hector Zenil
Pediatric high grade gliomas are lethal evolutionary disorders with stalled developmental trajectories and disrupted differentiation hierarchies. We integrate transcriptional and a…
Advancing the Scientific Method with Large Language Models: From Hypothesis to Discovery
Yanbo Zhang, Sumeer A. Khan, Adnan Mahmud +10
With recent Nobel Prizes recognising AI contributions to science, Large Language Models (LLMs) are transforming scientific research by enhancing productivity and reshaping the scie…
On the Limits of Self-Improving in Large Language Models: The Singularity Is Not Near Without Symbolic Model Synthesis
Hector Zenil
We formalise recursive self-training in Large Language Models (LLMs) and Generative AI as a discrete-time dynamical system. We prove that if the proportion of exogenous, externally…
A Computable Measure of Algorithmic Probability by Finite Approximations with an Application to Integer Sequences
Fernando Soler-Toscano, Hector Zenil
Given the widespread use of lossless compression algorithms to approximate algorithmic (Kolmogorov-Chaitin) complexity, and that lossless compression algorithms fall short at chara…
On the Algorithmic Nature of the World
Hector Zenil, Jean-Paul Delahaye
We propose a test based on the theory of algorithmic complexity and an experimental evaluation of Levin's universal distribution to identify evidence in support of or in contravent…
A Behavioural Foundation for Natural Computing and a Programmability Test
Hector Zenil
What does it mean to claim that a physical or natural system computes? One answer, endorsed here, is that computing is about programming a system to behave in different ways. This…
Numerical Evaluation of Algorithmic Complexity for Short Strings: A Glance into the Innermost Structure of Randomness
Jean-Paul Delahaye, Hector Zenil
We describe an alternative method (to compression) that combines several theoretical and experimental results to numerically approximate the algorithmic (Kolmogorov-Chaitin) comple…
Fractal dimension versus process complexity
Joost J. Joosten, Fernando Soler-Toscano, Hector Zenil
Complexity measures are designed to capture complex behavior and quantify *how* complex, according to that measure, that particular behavior is. It can be expected that different c…
Neurosymbolic Learning for Predicting Cell Fate Decisions from Longitudinal Single Cell Transcriptomics in Paediatric Acute Myeloid Leukemia
Abicumaran Uthamacumaran, Hector Zenil
Paediatric Acute Myeloid Leukemia is a complex adaptive ecosystem with high morbidity. Current trajectory inference algorithms struggle to predict causal dynamics in AML progressio…
A Decomposition Method for Global Evaluation of Shannon Entropy and Local Estimations of Algorithmic Complexity
Hector Zenil, Santiago Hernández-Orozco, Narsis A. Kiani +2
We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic com…
On the possible Computational Power of the Human Mind
Hector Zenil, Francisco Hernandez-Quiroz
The aim of this paper is to address the question: Can an artificial neural network (ANN) model be used as a possible characterization of the power of the human mind? We will discus…
The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probabilit…
Methods of Information Theory and Algorithmic Complexity for Network Biology
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
We survey and introduce concepts and tools located at the intersection of information theory and network biology. We show that Shannon's information entropy, compressibility and al…
Symmetry and Algorithmic Complexity of Polyominoes and Polyhedral Graphs
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
We introduce a definition of algorithmic symmetry able to capture essential aspects of geometric symmetry. We review, study and apply a method for approximating the algorithmic com…
Evaluating Network Inference Methods in Terms of Their Ability to Preserve the Topology and Complexity of Genetic Networks
Narsis A. Kiani, Hector Zenil, Jakub Olczak +1
Network inference is a rapidly advancing field, with new methods being proposed on a regular basis. Understanding the advantages and limitations of different network inference meth…
Assembly Theory Reduced to Shannon Entropy and Rendered Redundant by Naive Statistical Algorithms
Luan Ozelim, Abicumaran Uthamacumaran, Felipe S. Abrahão +4
Assembly Theory (AT) and its central measure, the assembly index (Ai), represent an invaluable opportunity to address some of the most persistent and widespread conflations and mis…
Fractal spatio-temporal scale-free messaging: amplitude modulation of self-executable carriers given by the Weierstrass function's components
Hector Zenil, Luan Carlos de Sena Monteiro
In many communication contexts, the capabilities of the involved actors cannot be known beforehand, whether it is a cell, a plant, an insect, or even a life form unknown to Earth.…
Compression-based investigation of the dynamical properties of cellular automata and other systems
Hector Zenil
A method for studying the qualitative dynamical properties of abstract computing machines based on the approximation of their program-size complexity using a general lossless compr…
An Optimal, Universal and Agnostic Decoding Method for Message Reconstruction, Bio and Technosignature Detection
Hector Zenil, Alyssa Adams, Felipe S. Abrahão +1
We present an agnostic signal reconstruction method for zero-knowledge one-way communication channels in which a receiver aims to interpret a message sent by an unknown source abou…
Algorithmic information distortions and incompressibility in uniform multidimensional networks
Felipe S. Abrahão, Klaus Wehmuth, Hector Zenil +1
This article presents a theoretical investigation of generalized encoded forms of networks in a uniform multidimensional space. First, we study encoded networks with (finite) arbit…
An Algorithmic Information Calculus for Causal Discovery and Reprogramming Systems
Hector Zenil, Narsis A. Kiani, Francesco Marabita +5
We demonstrate that the algorithmic information content of a system is deeply connected to its potential dynamics, thus affording an avenue for moving systems in the information-th…
Slime mould: the fundamental mechanisms of cognition
Jordi Vallverdu, Oscar Castro, Richard Mayne +7
The slime mould Physarum polycephalum has been used in developing unconventional computing devices for in which the slime mould played a role of a sensing, actuating, and computing…
Computable Model Discovery and High-Level-Programming Approximations to Algorithmic Complexity
Vladimir Lemusa, Eduardo Acuña, VÃctor Zamora +2
Motivated by algorithmic information theory, the problem of program discovery can help find candidates of underlying generative mechanisms of natural and artificial phenomena. The…
Coding-theorem Like Behaviour and Emergence of the Universal Distribution from Resource-bounded Algorithmic Probability
Hector Zenil, Liliana Badillo, Santiago Hernández-Orozco +1
Previously referred to as `miraculous' in the scientific literature because of its powerful properties and its wide application as optimal solution to the problem of induction/infe…
Some Computational Aspects of Essential Properties of Evolution and Life
Hector Zenil, James A. R. Marshall
While evolution has inspired algorithmic methods of heuristic optimisation, little has been done in the way of using concepts of computation to advance our understanding of salient…
Causality, Information and Biological Computation: An algorithmic software approach to life, disease and the immune system
Hector Zenil, Angelika Schmidt, Jesper Tegnér
Biology has taken strong steps towards becoming a computer science aiming at reprogramming nature after the realisation that nature herself has reprogrammed organisms by harnessing…
Quantifying Loss of Information in Network-based Dimensionality Reduction Techniques
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
To cope with the complexity of large networks, a number of dimensionality reduction techniques for graphs have been developed. However, the extent to which information is lost or p…
Training-free Measures Based on Algorithmic Probability Identify High Nucleosome Occupancy in DNA Sequences
Hector Zenil, Peter Minary
We introduce and study a set of training-free methods of information-theoretic and algorithmic complexity nature applied to DNA sequences to identify their potential capabilities t…
Un metodo estable para la evaluacion de la complejidad algoritmica de cadenas cortas
Hector Zenil, Jean-Paul Delahaye
It is discussed and surveyed a numerical method proposed before, that alternative to the usual compression method, provides an approximation to the algorithmic (Kolmogorov) complex…
Reprogramming Matter, Life, and Purpose
Hector Zenil
Reprogramming matter may sound far-fetched, but we have been doing it with increasing power and staggering efficiency for at least 60 years, and for centuries we have been paving t…
Patterns in Individual Blood Count Trajectories in the UK Biobank Characterise Disease-Specific Signatures and Anticipate Pan-Cancer Risk
Riya Nagar, Abicumaran Uthamacumaran, Adelaide de Vecchi +1
We investigate the longitudinal behaviour of blood markers from common haematological tests as a marker of disease and as a function of disease progression in a variety of conditio…
On sequential structures in incompressible multidimensional networks
Felipe S. Abrahão, Klaus Wehmuth, Hector Zenil +1
In order to deal with multidimensional structure representations of real-world networks, as well as with their worst-case irreducible information content analysis, the demand for n…
Algorithmic Data Analytics, Small Data Matters and Correlation versus Causation
Hector Zenil
This is a review of aspects of the theory of algorithmic information that may contribute to a framework for formulating questions related to complex highly unpredictable systems. W…
Numerical Investigation of Graph Spectra and Information Interpretability of Eigenvalues
Hector Zenil, Narsis A. Kiani, Jesper Tegnér
We undertake an extensive numerical investigation of the graph spectra of thousands regular graphs, a set of random Erdös-Rényi graphs, the two most popular types of complex netw…
The Future of Fundamental Science Led by Generative Closed-Loop Artificial Intelligence
Hector Zenil, Jesper Tegnér, Felipe S. Abrahão +17
Recent advances in machine learning and AI, including Generative AI and LLMs, are disrupting technological innovation, product development, and society as a whole. AI's contributio…
Simulation Intelligence: Towards a New Generation of Scientific Methods
Alexander Lavin, David Krakauer, Hector Zenil +21
The original "Seven Motifs" set forth a roadmap of essential methods for the field of scientific computing, where a motif is an algorithmic method that captures a pattern of comput…
Evolving Neural Networks through a Reverse Encoding Tree
Haoling Zhang, Chao-Han Huck Yang, Hector Zenil +3
NeuroEvolution is one of the most competitive evolutionary learning frameworks for designing novel neural networks for use in specific tasks, such as logic circuit design and digit…
A Quantitative Approach to Estimating Bias, Favouritism and Distortion in Scientific Journalism
Raghavendra Koushik, Hector Zenil
While traditionally not considered part of the scientific method, science communication is increasingly playing a pivotal role in shaping scientific practice. Researchers are now f…
Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
Hector Zenil, Fernando Soler-Toscano, Kamaludin Dingle +1
We show that numerical approximations of Kolmogorov complexity (K) applied to graph adjacency matrices capture some group-theoretic and topological properties of graphs and empiric…
Non-Random Data Encodes its Geometric and Topological Dimensions
Hector Zenil, Felipe S. Abrahão, Luan C. S. M. Ozelim
Based on the principles of information theory, measure theory, and theoretical computer science, we introduce a signal deconvolution method with a wide range of applications to cod…
Computation and Universality: Class IV versus Class III Cellular Automata
Genaro J. Martinez, Juan C. Seck-Tuoh-Mora, Hector Zenil
This paper examines the claim that cellular automata (CA) belonging to Class III (in Wolfram's classification) are capable of (Turing universal) computation. We explore some chaoti…
Algorithmic Probability-guided Supervised Machine Learning on Non-differentiable Spaces
Santiago Hernández-Orozco, Hector Zenil, Jürgen Riedel +3
We show how complexity theory can be introduced in machine learning to help bring together apparently disparate areas of current research. We show that this new approach requires l…
Measuring in-context algorithmic reasoning in language models against an exact Bayes-optimal standard
Hector Zenil, Luan Ozelim
Whether large language models perform genuine algorithmic reasoning or mere pattern completion is hard to test, because most benchmarks lack a ground truth for correct inductive in…
Assembly Theory is an approximation to algorithmic complexity based on LZ compression that does not explain selection or evolution
Felipe S. Abrahão, Santiago Hernández-Orozco, Narsis A. Kiani +2
We prove the full equivalence between Assembly Theory (AT) and Shannon Entropy via a method based upon the principles of statistical compression renamed `assembly index' that belon…
Quantifying Natural and Artificial Intelligence in Robots and Natural Systems with an Algorithmic Behavioural Test
Hector Zenil
One of the most important aims of the fields of robotics, artificial intelligence and artificial life is the design and construction of systems and machines as versatile and as rel…
Cross-boundary Behavioural Reprogrammability Reveals Evidence of Pervasive Universality
Jürgen Riedel, Hector Zenil
We exhaustively explore the reprogrammability capabilities and the intrinsic universality of the Cartesian product of the space of all possible computer programs o…
Approximations of Algorithmic and Structural Complexity Validate Cognitive-behavioural Experimental Results
Hector Zenil, James A. R. Marshall, Jesper Tegnér
Being able to objectively characterise the intrinsic complexity of behavioural patterns resulting from human or animal decisions is fundamental for deconvolving cognition and desig…
On Universality in Real Computation
Hector Zenil
Models of computation operating over the real numbers and computing a larger class of functions compared to the class of general recursive functions invariably introduce a non-fini…
On the Salient Limitations of the Methods of Assembly Theory and their Classification of Molecular Biosignatures
Abicumaran Uthamacumaran, Felipe S. Abrahão, Narsis A. Kiani +1
We demonstrate that the assembly pathway method underlying assembly theory (AT) is an encoding scheme widely used by popular statistical compression algorithms. We show that in all…
Minimal Algorithmic Information Loss Methods for Dimension Reduction, Feature Selection and Network Sparsification
Hector Zenil, Narsis A. Kiani, Alyssa Adams +5
We present a novel, domain-agnostic, model-independent, unsupervised, and universally applicable Machine Learning approach for dimensionality reduction based on the principles of a…
Emergence and algorithmic information dynamics of systems and observers
Felipe S. Abrahão, Hector Zenil
Previous work has shown that perturbation analysis in software space can produce candidate computable generative models and uncover possible causal properties from the finite descr…
A Review of Methods for Estimating Algorithmic Complexity: Options, Challenges, and New Directions
Hector Zenil
Some established and also novel techniques in the field of applications of algorithmic (Kolmogorov) complexity currently co-exist for the first time and are here reviewed, ranging…
Binarized Neural Networks Converge Toward Algorithmic Simplicity: Empirical Support for the Learning-as-Compression Hypothesis
Eduardo Y. Sakabe, Felipe S. Abrahão, Alexandre Simões +4
Understanding and controlling the informational complexity of neural networks is a central challenge in machine learning, with implications for generalization, optimization, and mo…
A Computable Piece of Uncomputable Art whose Expansion May Explain the Universe in Software Space
Hector Zenil
At the intersection of what I call uncomputable art and computational epistemology, a form of experimental philosophy, we find an exciting and promising area of science related to…
Rare Speed-up in Automatic Theorem Proving Reveals Tradeoff Between Computational Time and Information Value
Santiago Hernández-Orozco, Francisco Hernández-Quiroz, Hector Zenil +1
We show that strategies implemented in automatic theorem proving involve an interesting tradeoff between execution speed, proving speedup/computational time and usefulness of infor…
Integrative Adaptive Indexes from Noisy Routine Haematological Markers can Predict and Discriminate Health Status and Biological Age
Santiago Hernández-Orozco, Abicumaran Uthamacumaran, Francisco Hernández-Quiroz +2
For more than two decades, advances in personalised medicine and precision healthcare have largely been based on genomics and other omics data. These strategies aim to tailor inter…
Program-Size Versus Time Complexity, Speed-Up and Slowdown Phenomena in Small Turing Machines
Joost J. Joosten, Fernando Soler-Toscano, Hector Zenil
The aim of this paper is to undertake an experimental investigation of the trade-offs between program-size and time computational complexity. The investigation includes an exhausti…
Sloane's Gap. Mathematical and Social Factors Explain the Distribution of Numbers in the OEIS
Nicolas Gauvrit, Jean-Paul Delahaye, Hector Zenil
The Online Encyclopedia of Integer Sequences (OEIS) is made up of thousands of numerical sequences considered particularly interesting by some mathematicians. The graphic represent…
The World is Either Algorithmic or Mostly Random
Hector Zenil
I will propose the notion that the universe is digital, not as a claim about what the universe is made of but rather about the way it unfolds. Central to the argument will be the c…
On the Kolmogorov-Chaitin Complexity for short sequences
Jean-Paul Delahaye, Hector Zenil
A drawback of Kolmogorov-Chaitin complexity (K) as a function from s to the shortest program producing s is its noncomputability which limits its range of applicability. Moreover,…
Wolfram's Classification and Computation in Cellular Automata Classes III and IV
Genaro J. Martinez, J. C. Seck-Tuoh-Mora, Hector Zenil
We conduct a brief survey on Wolfram's classification, in particular related to the computing capabilities of Cellular Automata (CA) in Wolfram's classes III and IV. We formulate a…
Interacting Behavior and Emerging Complexity
Alyssa Adams, Hector Zenil, Eduardo Hermo Reyes +1
Can we quantify the change of complexity throughout evolutionary processes? We attempt to address this question through an empirical approach. In very general terms, we simulate tw…
Turing Minimalism and the Emergence of Complexity
Hector Zenil
Not only did Turing help found one of the most exciting areas of modern science (computer science), but it may be that his contribution to our understanding of our physical reality…
Formal Definitions of Unbounded Evolution and Innovation Reveal Universal Mechanisms for Open-Ended Evolution in Dynamical Systems
Alyssa M Adams, Hector Zenil, Paul CW Davies +1
Open-ended evolution (OEE) is relevant to a variety of biological, artificial and technological systems, but has been challenging to reproduce in silico. Most theoretical efforts f…
Rule Primality, Minimal Generating Sets, Turing-Universality and Causal Decomposition in Elementary Cellular Automata
Jürgen Riedel, Hector Zenil
We introduce several concepts such as prime and composite rule, tools and methods for causal composition and decomposition. We discover and prove new universality results in ECA, n…
Levels of Abstraction and the Apparent Contradictory Philosophical Legacy of Turing and Shannon
Hector Zenil
In a recent article, Luciano Floridi explains his view of Turing's legacy in connection to the philosophy of information. I will very briefly survey one of Turing's other contribut…
Can Complexity and Uncomputability Explain Intelligence? SuperARC: A Test for Artificial Super Intelligence Based on Recursive Compression
Alberto Hernández-Espinosa, Luan Ozelim, Felipe S. Abrahão +1
We introduce an increasing-complexity, open-ended, and human-agnostic metric to evaluate foundational and frontier AI models in the context of Artificial General Intelligence (AGI)…