Publications (20)
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…
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…
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…
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…
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…
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…
Forgetting complex propositions
David Fernández-Duque, Ãngel Nepomuceno-Fernández, Enrique Sarrión-Morrillo +2
This paper uses possible-world semantics to model the changes that may occur in an agent's knowledge as she loses information. This builds on previous work in which the agent may f…
Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility
Hector Zenil, Fernando Soler-Toscano, Jean-Paul Delahaye +1
We propose a measure based upon the fundamental theoretical concept in algorithmic information theory that provides a natural approach to the problem of evaluating -dimensional…
A geometric protocol for cryptography with cards
Andrés Cordón-Franco, Hans van Ditmarsch, David Fernández-Duque +1
In the generalized Russian cards problem, the three players Alice, Bob and Cath draw a,b and c cards, respectively, from a deck of a+b+c cards. Players only know their own cards an…
A meta-modal logic for bisimulations
Alfredo Burrieza, Fernando Soler-Toscano, Antonio Yuste-Ginel
We propose a modal study of the notion of bisimulation. Our contribution is threefold. First, we extend the basic modal language with a new modality $\nbi$, whose intended meaning…
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…
A secure additive protocol for card players
Andres Cordon-Franco, Hans van Ditmarsch, David Fernandez-Duque +2
Consider three players Alice, Bob and Cath who hold a, b and c cards, respectively, from a deck of d=a+b+c cards. The cards are all different and players only know their own cards.…
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…
Which is the least complex explanation? Abduction and complexity
Fernando Soler-Toscano
It may happen that for a certain abductive problem there are several possible explanations, not all of them mutually compatible. What explanation is selected and which criteria are…
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…
A colouring protocol for the generalized Russian cards problem
Andrés Cordón-Franco, Hans van Ditmarsch, David Fernández-Duque +1
In the generalized Russian cards problem, Alice, Bob and Cath draw , and cards, respectively, from a deck of size . Alice and Bob must then communicate their enti…
Structural stability of invasion graphs for Lotka--Volterra systems
Pablo Almaraz, Piotr Kalita, José A. Langa +1
In this paper, we study in detail the structure of the global attractor for the Lotka--Volterra system with a Volterra--Lyapunov stable structural matrix. We consider the invasion…
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…
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…