Hector Zenil
hector.zenil [at] algorithmicnaturelab [dot] org




I split my research time between Stockholm and Oxford. I am a research associate in algorithmic information and computational biology at the Unit of Computational Medicine of the Karolinska Institute in Sweden. My research focuses on applying information theory and complexity science to genomics, synthetic and network biology. With backgrounds in math, computer science and philosophy, I think of myself as a kind of experimental philosopher or a computational natural scientist. (Greg Chaitin once referred to me as a "new kind of practical theoretician").

I am also in charge of the ItBit Programme on Physical and Computational Sciences at Oxford and act as head of the Algorithmic Nature Group (the lab responsible for the Online Algorithmic Complexity Calculator and the Human Randomness Perception and Generation Project); co-director of the Paris-based lab LABORES for the Natural and Digital Sciences; and associate member of the PARIS Reasoning team (Paris 8) undertaking research on algorithmic psychometrics and subjective randomness.

I have been an R&D fellow and later senior research associate for Wolfram Research in the U.S. since 2006 in Stephen Wolfram's science group in Boston. I worked on the Wolfram|Alpha project from its inception to its public release in aspects of data mining, computational linguistics, and fast prototyping. I am also a member of the Foundational Questions Institute (FQXi); an honorary founding associate of ASSRU (Economics Dept. Trento, Italy); a member of the Turing Centenary Advisory Committee in the UK and member of the national researchers body (SNI) in Mexico.

 

Previously:

Postdoc (2011-2013)
Behavioural and Evolutionary Theory Lab

Department of Computer Science
University of Sheffield, UK

Visiting Scholar (Spring term 2008)
Carnegie Mellon University, USA

Intern (Summer 2007)
MIT - NASA Mars Gravity Biosatellite, USA

PhD. in Computer Science (2011)
University of Lille I
, France

MPhil. in Logic (LoPHISS) (2005)
University of
Paris I Panthéon-Sorbonne, France

BSc. in Mathematics, UNAM, Mexico (2004)

PhD. in Philosophy of Science (exp. 2014)
IHPST (Paris 1/ENS Ulm/CNRS), France

 


 


Research Interests

  • Tradeoffs of complexity measures: how entropy, algorithmic randomness, logical depth, algorithmic probability, computational complexity and fractal dimension can be connected (see e.g. papers 3, 4, 6, 19 and proceedings 6 and 11). Contributing with the only method other than lossless compression to approximate the Kolmogorov complexity of strings (see papers 5, 23). Applications to many areas (see papers 2, 7, 8, 20).
  • Controllability and programmability of complex systems: devising strategies to understand, test and reprogram artificial and natural systems as models of computation (see e.g. papers 9, 12, 18) devising also 2 measures for testing the algorithmicity and programmability of a system (see also in proceedings 10 and in collections 5).
  • Spatial complexity, molecular and natural computing: contributing with methods to evaluate 2-dimensional complexity (previously identified by Feldman as an open problem, see papers 16, 18, 22).
  • Information theory and algebraic graph theory: contributed a solution to the challenge of network complexity (previously identified by Gell-mann and Feldman as an open problem, see paper 22).
  • Emergence of organization and structure: providing numerical evidence in favour of Levin's universal distribution and Solomonoff's program-size bias towards simplicity (see papers 12, 15, 18, 23).
  • Computational, synthetic and network biology: novel applications of information theory to genetic regulatory networks and other biological interaction networks (see papers 18, 22 and proceedings 10 and 13).
  • Cellular automata theory: contributing a novel formal behavioural classification based on asymptotic behaviour, giving answer to one of Wolfram's open question on the fraction of behaviour classes in CA rule spaces (see paper 17), a classification by compression (paper 1) and a new proof of universality in Elementary Cellular Automata (ECA) (soon available).


Latest Events

 

 

Media Coverage

  • Our work and paper (see paper 20) with colleagues J.-P. Delahaye, N. Gauvrit and F. Soler-Toscano was featured in a short note by the French newspaper Le Monde in its science section under the title Le cerveu: probabilist par nature? (I find the title misleading, what our paper actually suggests is that the human brain develops an algorithmic nature not a classical probabilistic one, this based on actual experiments to explain the nature of subjective randomness).

 

 

Selected Journal Papers
(# joint first author)

25. Turing Minimalism and the Emergence of Complexity
H. Zenil
The Rutherford Journal (accepted) [preprint]

24. Natural scene statistics mediate the perception of image complexity
N. Gauvrit, F. Soler-Toscano, H. Zenil
Visual Cognition [preprint, online] doi: 10.1080/13506285.2014.950365

23. Calculating Kolmogorov Complexity from the Output Frequency Distributions of Small Turing Machines
F. Soler-Toscano, H. Zenil#, J.-P. Delahaye and N. Gauvrit
PLoS ONE 9(5): e96223, 2014. [free online, data, online program, Mathematica API, R package] doi:10.1371/journal.pone.0096223

22. Correlation of Automorphism Group Size and Topological Properties with Program-size Complexity Evaluations of Graphs and Complex Networks
H. Zenil
, F. Soler-Toscano, K. Dingle and A. Louis
Physica A: Statistical Mechanics and its Applications, vol. 404, pp. 341–358, 2014. [online, preprint] DOI: 10.1016/j.physa.2014.02.060

21. Complexity Measurement Based on Information Theory and Kolmogorov Complexity
L. Ting Lui, G. Terrazas, H. Zenil, C. Alexander and N. Krasnogor
Artificial Life (in press)

20. Algorithmic complexity for short binary strings applied to psychology: a primer
N. Gauvrit, H. Zenil, F. Soler-Toscano and J.-P. Delahaye
Behavior Research Methods, vol. 46-3, pp 732-744, 2013 [preprint, online] DOI: 10.3758/s13428-013-0416-0

19. Correspondence and Independence of Numerical Evaluations of Algorithmic Information Measures
F. Soler-Toscano, H. Zenil#, J.-P. Delahaye and N. Gauvrit
Computability, vol. 2, no. 2, pp 125-140, 2013. DOI 10.3233/COM-13019 [online, preprint]

18. Exploring Programmable Self-Assembly in Non DNA-based Computing
G. Terrazas, H. Zenil and N. Krasnogor
Natural Computing, vol 12(4): 499--515, 2013. DOI: 10.1007/s11047-013-9397-2 [online, preprint]

17. Asymptotic Behaviour and Ratios of Complexity in Cellular Automata Rule Spaces
H. Zenil
and E. Villarreal-Zapata
International Journal of Bifurcation and Chaos vol. 13, no. 9, 2013. [preprint] DOI: 10.1142/S0218127413501599

16. Two-Dimensional Kolmogorov Complexity and Validation of the Coding Theorem Method by Compressibility
H. Zenil
, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit
In revision. Preprint on ArXiv:1212.6745 [cs.CC], [preprint]

15. Turing Patterns with Turing Machines: Emergence and Low-level Structure Formation
H. Zenil
Natural Computing,
vol. 12(2): 291-303, 2013, DOI:10.1007/s11047-013-9363-z [online, preprint]

14. Life as Thermodynamic Evidence of Algorithmic Structure in Natural Environments
H. Zenil, C. Gershenson, J.A.R. Marshall and D. Rosenblueth
Entropy, 14(11), 2173-2191, 2012. [online] DOI: 10.3390/e14112173

13. Computation and Universality: Class IV versus Class III Cellular Automata
G.J. Martinez, J.C. Seck-Touh-Mora and H. Zenil
Journal of Cellular Automata, vol. 7, no. 5-6, pp. 393-430, 2013.

12. Algorithmicity and Programmability in Natural Computing with the Game of Life as an In Silico Case Study
H. Zenil
Journal of Experimental & Theoretical Artificial Intelligence DOI:10.1080/0952813X.2014.940686 (in press)

11. Some Aspects of Computation Essential to Evolution and Life
H. Zenil and J.A.R. Marshall
Ubiquity (ACM), vol. 2013, no. April (2013), pp 1-16. [online, preprint]

10. On the Dynamic Qualitative Behaviour of Universal Computation
H. Zenil
Complex Systems, 20-3, pp 265-277, 2012. [online,preprint]

9. What is Nature-like Computation? A Behavioural Approach and a Notion of Programmability
H. Zenil
Philosophy & Technology (special issue on the History and Philosophy of Computing), 2013. [online, preprint] DOI: 10.1007/s13347-012-0095-2

8. Sloane’s Gap: Do Mathematical and Social Factors Explain the Distribution of Numbers in the OEIS?
N. Gauvrit, J.-P. Delahaye and H. Zenil
Journal of Humanistic Mathematics, vol. 3, no. 1, pp. 3-19, 2013. [preprint, featured in Numberphile] DOI: 10.5642/jhummath.201301.03

7. Algorithmic Complexity of Financial Motions
L. Ma, O. Brandouy, J.-P. Delahaye and H. Zenil
Research in International Business and Finance, vol. 30, pp. 336-347, 2014. (published online in 2012)
[online,preprint] DOI: 10.1016/j.ribaf.2012.08.001

6. Program-size versus Time complexity, Slowdown and speed-up phenomena in the micro-cosmos of small Turing machines
J.J. Joosten, F. Soler Toscano and H. Zenil#
International Journal of Unconventional Computing, vol. 7, no. 5, pp. 353-387, 2011. [preprint]

5. Numerical Evaluation of the Complexity of Short Strings: A Glance Into the Innermost Structure of Algorithmic Randomness
J.-P. Delahaye and H. Zenil#
Applied Mathematics and Computation 219, pp. 63-77, 2012. [preprint] DOI:10.1016/j.amc.2011.10.006 (online 2011)

4. Empirical Encounters with Computational Irreducibility and Unpredictability
H. Zenil, F. Soler-Toscano and J.J. Joosten
Minds and Machines, vol. 22, Number 3, pp. 149-165, 2012. [preprint]. DOI: 10.1007/s11023-011-9262-y

3. Image Information Content Characterization and Classification by Physical Complexity
H. Zenil, J.-P. Delahaye and C. Gaucherel
Complexity, vol. 17-3, pages 26-42, 2012. [preprint] DOI:10.1002/cplx.20388

2. An Algorithmic Information-theoretic Approach to the Behaviour of Financial Markets
H. Zenil and J.-P. Delahaye
Journal of Economic Surveys, vol. 25-3, pp. 463, 2011. [preprint]
DOI:10.1111/j.1467-6419.2010.00666.x

1. Compression-based Investigation of the Dynamical Properties of Cellular Automata and Other Systems
H. Zenil
Complex Systems, vol. 19, No. 1, pp. 1-28, 2010. [free online]



In Proceedings

14. H. Zenil, V. Kannan, J. Tegnér
Gene Sequence Walks, Visualizing Biological Data conference (EMBO - EMBL VizBi 2014), Heildeberg, Germany (poster and lighting talk).

13. H. Zenil, N.A. Kiani and J. Tegner
Algorithmic complexity of motifs clusters superfamilies of networks
IEEE International Conference on Bioinformatics and Biomedicine, Shanghai, China 2013.

12. H. Zenil
Algorithmic Complexity of Animal Behaviour: From Communication to Cognition. Theory and Practice of Natural Computing Second International Conference, TPNC 2013. Cáceres, Spain, December 3-5, 2013 (poster), Cáceres, Spain

11. J.J. Joosten, F. Soler-Toscano, H. Zenil
Fractal Dimension of Space-time Diagrams and the Runtime Complexity of Small Turing Machines
In T. Neary and M. Cook (Eds.): Machines, Computations and Universality (MCU 2013), EPTCS 128, 2013, pp. 29-30, DOI: 10.4204/EPTCS.128.9. [abstract, presentation]

10. H. Zenil, G. Ball and J. Tegnér
Testing Biological Models for Non-linear Sensitivity with a Programmability Test
In P. Liò, O. Miglino, G. Nicosia, S. Nolfi and M. Pavone (eds), Advances in Artificial Intelligence, ECAL 2013, pp. 1222-1223, MIT Press, 2013. DOI: http://dx.doi.org/10.7551/978-0-262-31719-2-ch188 [online]

9. S. Hernández-Orozco, F. Hernández-Quiroz and H. Zenil
Sparsity of Non-trivial Proving Speed-up in Random Systems of Propositional Calculus
In Paola Bonizzoni, Vasco Brattka, Benedikt Löwe (eds.), The Nature of Computation, Logic, Algorithms, Applications; 9th Conference on Computability in Europe, CiE 2013, 2013.

8. H. Zenil
A Turing Test-Inspired Approach to Natural Computation
In G. Primiero and L. De Mol (eds.), Turing in Context II, Historical and Contemporary Research in Logic, Computing Machinery and Artificial Intelligence. Proceedings by the Royal Flemish Academy of Belgium for Science and the Arts, Belgium, 2013.

7. H. Zenil
A Behavioural Foundation for Natural Computing and a Programmability Test
In G. Dodig-Crnkovic and R. Giovagnoli (eds), Computing Nature: Turing Centenary Perspective, SAPERE Series vol. 7, pp. 87-113, 2013. [online, preprint] [conference picture] AISB/IACAP Turing World Congress 2012, Birmingham, UK (invited talk)
.

6. H. Zenil
From Computer Runtimes to the Length of Proofs: With an Algorithmic Probabilistic Application to Waiting Times in Automatic Theorem Proving
In M.J. Dinneen, B. Khousainov, and A. Nies (Eds.), Computation, Physics and Beyond International Workshop on Theoretical Computer Science, WTCS 2012, LNCS 7160, pp. 223-240, Springer, 2012. [preprint] DOI:10.1007/978-3-642-27654-5_17

5. L. Ma, O. Brandouy, J.-P. Delahaye and H. Zenil
Algorithmic Complexity of Financial Motions
In S. Kinsella, New Directions in Modeling International Finance, Routledge Advances Series on Experimental and Computable Economics, 2012. [preprint]

4. H. Zenil
What Randomness for What Biological Process?
XXIII SITGES, Understanding and Managing Randomness in Physics, Chemistry and Biology, University of Barcelona, p.98, Spain, 2012.

3. J.J. Joosten, H. Zenil and F. Soler-Toscano
Fractal Dimension as an Indication of the Terminating Runtime of Discrete Dynamical Systems, (abstract p. 214) in S. Thurner M. Szell (eds), Löcker Verlag, European Conference on Complex Systems (ECCS'11), 2011.

2. J.J. Joosten, F. Soler-Toscano and H. Zenil#
Program-size versus Time complexity, Slowdown and speed-up phenomena in the micro-cosmos of small Turing machines 
In H. Guerra (ed.). Physics and Computation 2010, CAMIT, 3rd International Workshop on Physics and Computation 2010. [PDF]

1. J.J. Joosten, F. Soler-Toscano and H. Zenil#
Complejidad descriptiva y computacional en máquinas de Turing pequeñas
Actas de las V Jornadas Ibéricas, Lógica Universal e Unidade da Ciência, CFCU 2010. [preprint]

 

In Collections


12. H. Zenil
On the Complex Behaviour of Natural and Artificial Machines and Systems

In F.P. Bonsignorio, A.P. del Pobil, E. Messina, J. Hallam (eds.), Metrics of sensory motor integration in robots and animals, How to measure the success of bio-inspired solutions with respect to their natural models, and against more ‘artificial’ solutions?, Springer Cosmos Series, Cognitive Systems Monographs, Springer, (to appear) [preprint]

11. H. Zenil and J. Tegnér
Methods of information theory and algorithmic complexity for network biology
In M. Elloumi,  C.S. Iliopoulos, J.T.L. Wang and A.Y. Zomaya (eds.), Pattern Recognition in Computational Molecular Biology: Techniques and Approaches Wiley Book Series on Bioinformatics: Computational Techniques and Engineering, Wiley-Blackwell, John Wiley & Sons Ltd., (to appear) [preprint]

10. The Π Research Network (H. Zenil i.a.), Algorithmic Information Theory, The Philosophy of Information An Introduction, Society for the Philosophy of Information, 2013 [online]

9. H. Zenil
Turing, Randomness and Economics
In K. Velupillai and S-H. Chen (eds), Mathematics in Economics - Foundations, Philosophy and Epistemology, World Scientific (forthcoming) [preprint]

8. G.J. Martinez, J.C. Seck-Touh-Mora and H. Zenil
Wolfram's Classification and Computation in Cellular Automata Classes III and IV
In H. Zenil (ed), Irreducibility and Computational Equivalence: Wolfram Science 10 Years After the Publication of A New Kind of Science, Springer, 2013 [preprint].

7. H. Zenil, and J.-P. Delahaye
Un método estable para la evaluación de la complejidad algorítmica de cadenas cortas (A Stable Method for the Evaluation of the Algorithmic Complexity of Short Strings).
In G.J. Martinez, H. Zenil and C.R. Stevens (eds), Complex Systems as Computing Models, Luniver Press, 2011. [preprint]

6. H. Zenil and J.-P. Delahaye
An Algorithmic Information-theoretic Approach to the Behaviour of Financial Markets.
In S. Zambelli, D.A.R. George (eds.) Nonlinearity, Complexity and Randomness in Economics: Towards Algorithmic Foundations for Economics, Wiley-Blackwell, 2011. [preprint]

5. H. Zenil and J-P. Delahaye
On the Algorithmic Nature of the World. In G. Dodig-Crnkovic and M. Burgin (eds), Information and Computation, World Scientific Publishing Company, 2010. [preprint]

4. J-P. Delahaye and H. Zenil#
On the Kolmogorov-Chaitin complexity for short sequences
In C. Calude (ed)
Randomness and Complexity: From Leibniz to Chaitin, World Scientific Publishing Company, 2007. [preprint]

3. H. Zenil and F. Hernandez-Quiroz
On the Possible Computational Power of the Human Mind
In Worldviews, Science and Us, Philosophy and Complexity, C. Gershenson, D. Aerts, and B. Edmonds (eds), World Scientific, 2007. [preprint]

2. J.J. Joosten, F. Soler-Toscano, H. Zenil#
Complejidad descriptiva y computacional en máquinas de Turing pequeñas
En Lógica Universal e Unidade da Ciência, Centro de Filosofia das Ciências da Universidade de Lisboa, pp. 11--32, 2011. [preprint]

1. H. Zenil
El Universo Algorítmico
In, O. Miramontes and K. Volke (eds.) Fronteras de la Física en el Siglo XXI, CopIt arXives, UNAM, 2013 [PDF]



Books & Edited Volumes

 

  • I. Zelinka, A. Sanayei, H. Zenil and O.E. Rössler (eds), How Nature Works, Complexity in Interdisciplinary Research and Applications, Series: Emergence, Complexity and Computation, Vol. 5, Springer, 2013.
  • H. Zenil, F. Soler-Toscano, J.-P. Delahaye and N. Gauvrit, Methods and Applications of Kolmogorov Complexity, Springer, forthcoming 2014.

 

Theses

  • L'approche algorithmique de l'aléatoire, thesis fulfilling the dissertation requirement for the Degree of Doctor of Philosophy under the direction of J. Mosconi, IHPST (Paris 1/ENS Ulm/CNRS). (in progress)
  • Calcul et hyper calcul, (mémoire) fulfilling the dissertation requirement for the degree of Masters (Logic) under the direction of Jacques Dubucs at the University of Paris 1 Panthéon-Sorbonne, 2006. 16/20.
  • Encaje de las Redes Neuronales Recurrentes Analógicas en la Jerarquía Aritmética fulfilling the requirement for the B.Sc. (Math) degree, under advice of F. Hernández-Quiroz, Facultad de Ciencias, UNAM, 2005.

 

Selected Essays and Reviews

  • H. Zenil, The Seemingly Contradictory Philosophical Legacy of Turing and Shannon, AISB Quarterly no. 138 pp. 9--15, 2014. [PDF]
  • H. Zenil and J.A.R. Marshall
    Some Aspects of Computation Essential to Evolution and Life
    Ubiquity (ACM), vol. 2013, no. April (2013), pp 1-16. [online, preprint]
  • H. Zenil, Complejidad y Aleatoriedad, Ciencia (número especial de Turing), Academia Mexicana de Ciencias, vol 64-4, 2013. [online]. The outstanding cover of the special issue here. And the full article here.
  • A. German and H. Zenil, Afterword to Konrad Zuse's Calculating Space (Rechnender Raum)--The MIT translation--In A Computable Universe, World Scientific, 2012. [PDF]
  • H. Zenil, Introducing the Computable Universe, Introduction to A Computable Universe (foreword by Roger Penrose), World Scientific, 2012. [PDF]
  • H. Zenil
    An Algorithmic Approach to Information and Meaning
    APA Newsletter on Philosophy and Computers, vol. 11, No. 1, 2011. [online]
  • H. Zenil
    Information Theory and Computational Thermodynamics: Lessons for Biology from Physics
    Information 3, no. 4: 739-750, 2012. [online] DOI: :10.3390/info3040739
  • H. Zenil
    The Complexity of Simple Programs: Workshop Report from Cork, Ireland
    Bulletin of the European Association for Theoretical Computer Science (BEATCS), 2009.
  • H. Zenil
    Très courte enquête sur l'extension non-triviale de la logique de propositions à la logique du premier et deuxième ordre
    2005. [PDF]

 

 

Software

Network and Computational Biology

  1. Cospectrality and duality (forthcoming)
  2. Complex Networks (random, scale-free and small world)
  3. World Metro Networks
  4. Generating Random DNA Sequences (with GC content per species)
  5. Network motifs and graphlets

 

Information Theory, Computational Lingustics & Complexity Theory

  1. Fractal Dimension versus Time Computational Complexity in Turing Machines
  2. Complexity: an R-package to enable measures of algorithmic complexity (with N.Gauvrit, H.Singmann and F.Soler)
  3. Block Decomposition Method (soon available in Perl, Python, Java, C++, Pascal and Mathematica, w/F.Soler)

 

Discrete Math, Mathematical Logic & Combinatorics

 

Automata, Normality & Pseudorandomness

  1. Country Data and Benford's Law
  2. Champernowne Constant
  3. Prime Numbers Gaps
  4. Collatz Sequence Paths
  5. Distribution of Primes
  6. Digit Frequencies in the Copeland-Erdos Constant
  7. Small Turing Machines with Halting State: Enumeration and Running on a Blank Tape

 

 

Thesis Subjects for New Students

  • Graph theoretic properties of network motifs ("topological paving", network reconstruction, etc)
  • Granular and cellular complex system analysis using renormalization group techniques
  • Mathematical topology, big data analysis and information theory
  • Applications of the block decomposition method to image segmentation and classification
  • Algorithmic randomness and topological properties of boolean networks
  • The asymptotic behaviour of ECA rule 73 (walls investigation). Simulation of CAs by other CAs.
  • Computation and universality in busy beaver TMs.

If interested and funded (or with a funding idea), contact me for further details.




Selected Online Presentations (SlideShare)

Information Theory and Programmable Medicine
(recently uploaded: 314 views)

Fractal Dimension of Space-time Diagrams and the Runtime Complexity of Small Turing Machines
(since September 2013: 699 views)

Information Content of Complex Networks
(since September 2013: 1202 views)

L’approche algorithmique de l’aléatoire
(since 2012: 2771 views)

 

Organizing, Reviewing & Committee Memberships

 


Lecturing, Recent & Forthcoming Talks

    2014
  • Invited speaker: UNESCO UniTwin CS-DC e-Kickoff, June 23-26, 2014. Talk title: The Online Algorithmic Complexity Calculator (OACC): From Sequence Complexity to Graph Complexity.
  • Invited speaker. Talk title: Applications of algorithmic complexity to network science and synthetic biology, Conference on Computability, Complexity and Randomness (CCR), 9-13 June, 2014 in Singapore.
  • Plenary speaker. Talk title: Information Biology, The Annual Meeting of the International Association for Computing and Philosophy (IACAP) 2014, 2-4, July, Thessaloniki, Greece.
  • Invited talk. Talk title: Cognition, Information and Subjective Computation, Representation of Reality: Humans, Animals and Machines, 1-4 April, AISB50, 2014, London, UK.

 


Awards & Grants

  • Foundational Questions Institute (FQXi) mini-grant awarded by way of the Silicon Valley Community Foundation for travel support in the context of my "The Nature of Computation
    and the Physics of Information"
    , (FQXi-MGA-1316), 2013-2014.
  • Appointed member of the National Researchers Body (Sistema Nacional de Investigadores--SNI) of the National Council of Science and Technology of Mexico (CONACyT), 2012.
  • Foundational Questions Institute (FQXi) mini-grant awarded by way of the Silicon Valley Community Foundation for the project "Computation and Biology", (No. FQXi-MGA-1212) 2012-2013.
  • Foundational Questions Institute (FQXi) mini-grant awarded by way of the Silicon Valley Community Foundation for the project "Computation and Time" (no. 2011-93849 (4661)), 2011-2012.
  • Winner in the Computational Imagery category of the "2011 Kroto Institute Scientific Image Competition". Image entitled "Visualising the Computational Universe: Runtime Space in a Peano Curve", 2011.
  • 3rd Place Prize "Reality: Digital or Analog" Contest 2011, awarded by the Foundational Questions Institute (Essay title: "The World is Either Algorithmic or Mostly Random") announced at the World Science Festival, NYC, 2011.
  • Travel support by the British Society for the Philosophy of Science through the University of Leeds, 2012.
  • Early nominated to the MIT Technology Review (Spanish version) annual list of 35 INNOVATORS UNDER 35, 2012.
    Bourse aux jeunes chercheurs Comité National Français d'Histoire et de Philosophie des Sciences, 2011.
  • Ministère de l'Enseignement Supérieur et de la Recherche (bourse de mobilité aires culturelles), 2007, University of Paris.
  • Association for Symbolic Logic (ASL) Travel Grant Award (CiE 06, Swansea UK)
  • NSF and the New England Complex Institute (NECSI) (ICCS06-Boston, USA)
  • Université de Lille III, Kurt Gödel: The Writings, Maison de la Recherche 2006, Lille, France.
  • Isaac Newton Institute for Mathematical Sciences, Cambridge University, UK (visiting fellow, Workshop LAAW04, Wolfson Court, Girton College, UK), 2006.
  • Masters and PhD fellowships from CONACYT and the French Ministry of Education, 2005-2011.

 

 

Volunteering & Internships
Massachusetts Institute of Technology (MIT)
Summer 2007
Mars Gravity Biosatellite team

Supporting member of the software engineering team for the program, in charge of assembling, reviewing and enhancing software requirements and flowdown. Project co-sponsored by the NASA.

The International Wikimania Conference
Summer 2006

for the Wikimedia Foundation, Inc. (the Wikipedia Foundation)
Wikimedia Organization Team, July-August, Cambridge, Massachusetts, U.S.A.

Massachusetts Institute of Technology (MIT)
Summer 2006
Artificial Gravity Project (test subject)
Man-Vehicle Laboratory, August, Cambridge, Massachusetts, U.S.A.

Mexican Consulate in Seattle, WA.
December 2003-January 2004

Documentation and Consular Activities
Seattle, Washington, U.S.A.

 


An uncomputable picture of uncomputable art: This picture, titled “Visualizing the Computational Universe: Runtime Space in a Peano Curve," won me 1st. prize in the Computational Imagery category of the "2011 Kroto Institute Scientific Image Competition" held in the UK. It represents a small slice of the computational universe of all possible computer programs. Each pixel represents a computer program with empty input running on an abstract computer (a Turing machine). The color indicates the runtime of the program upon completion of its computation. The darker a pixel the longer the program took to produce its output. White pixels are computer programs that do not produce any output because they never halt (just as happens when your computer hangs forever sometimes making you reboot). Red pixels are the computer programs that take the longest time—relative to other programs of the same size-- before finishing (they are also called Busy Beavers). I call this color type coding the computability spectrum. Programs were sorted by size from smallest to largest (in terms of number of instructions) in such a way that one could be certain that any program would eventually be reached (including versions of MS Windows and Angry Birds that can be encoded as one-run computer programs). Because there is no upper limit to the size of programs, the space of all computer programs is infinite but discrete, perhaps mirroring our own world. Because an enumeration of computer programs is linear (you start with program 1, then proceed to program 2, and so on) pixels depicted in this 2-dimensional figure are disposed along a "space-filling" Peano curve. This is a curve that guarantees that 2 contiguous elements in the enumeration remain as close as possible to each other in the 2D configuration. The picture has the striking particularity that it is ultimately uncomputable. Imagine you point a telescope and take a picture of an object in the computational universe for which some pixel values cannot be determined, not only in practice but in principle-- that is, no matter how good your camera, or how many terapixels some future version of it may have. This slide of the computational universe was only possible because it is a tiny region of short computer programs for which all pixels can be determined by zooming in deep enough. However, Gödel and Turing proved that if you zoomed out to a larger view of the computational universe, the picture would l begin to look completely blurry because pixel colors would not be determinable . In other words this picture is the inverse equivalent of Hubble's Deep Field space--the larger the space field the blurrier. While we can only have access to the visible universe determined by the speed of light, we can only see a small part of the computational universe due to unattainable limits. Most of the computational space will remain unknowable, not due to a limitation of resources but due to a fundamental limitation from the the digital world and possibly of our own reality. Only marginal improvements to this picture are possible. While the picture is ultimately uncomputable and unattainable, one can make an informed guess as to how it would look. The theory that would tell you the average color of the picture at a greater scale, even if uncomputable, is the theory of algorithmic probability also closely related to what is known as the Chaitin Omega number. It turns out that the picture will be mostly white, as in an ever expanding universe, finding computer programs that halt and produce something becomes increasingly harder. Indeed, most programs will never halt, and those that do will do so relatively quickly in proportion to their size, as Calude has theoretically found and I have numerically confirmed. Algorithmic probability also tells us that most programs will produce the same output, and only those rare ones producing different outputs will produce random-looking digital sequences. In other words, among the computer programs that do produce an output, most of them will be highly ordered, as if they were creating a universe of sparse but highly ordered patterns out of nothing (remember these programs run with no input). Some of these programs that produce the same output may do so faster than others, but precisely how much faster some program may be is another an open foundational question and one of the greatest challenges in mathematics and computer science. If it were possible to find a program considerably faster than any other, then everything could be computed faster and faster, regardless of the apparent difficulty of a program.
I hereby give permission to reproduce this figure as a pedagogical tool for explaining deep and fundamental aspects of our reality. Just mention the source and if possible drop me a line. You can create your own too, and improve on mine (I did calculate the one that cannot be further improved upon without including undetermined pixels). If you do so I would love to know about it. You may also need to ask permission of Springer Verlag, as this picture was published in my paper From Computer Runtimes to the Length of Proofs: With an Algorithmic Probabilistic Application to Waiting Times in Automatic Theorem Proving. In M.J. Dinneen, B. Khousainov, and A. Nies (Eds.), Computation, Physics and Beyond, International Workshop on Theoretical Computer Science, WTCS 2012, LNCS 7160, pp.223-240, 2012.

 

 


Pictures and Videos

Hector Zenil, Stephen Wolfram, Paul Davies, Ugo Pagallo, Gregory Chaitin, Cristian Calude, Karl Svozil, Gordana Dodig-Crnkovic and John Casti
From left to right:
H. Zenil, Stephen Wolfram, Paul Davies, Ugo Pagallo, Greg Chaitin, Cris Calude,
Karl Svozil, Gordana Dodig-Crnkovic and John Casti.
Invited Speakers, NKS Conference, University of Vermont, USA. 2007.
(Picture by Sally McCay)


 

With Per Martin-Löf (student of Komogorov) having
lunch at the Maison de la Recherche, Paris 2010, France

 

 

With Greg Chaitin at his office in Yorktown, New York
IBM Thomas J. Watson Research Center, 2006, USA

 

 

Moderating a roundtable featuring (in order from left to right):
Greg Chaitin, Ed Fredkin, George Csicsery, Tony Leggett, Cris Calude, Tom Toffoli
and Stephen Wolfram
on the subject: What is Computation? How does nature compute?
University of Indiana Bloomington, 2008, USA

 

 


Lecturing at Mälardalen University, Sweden
CDT403 Research Methods in Natural Sciences and Engineering.


 

Space Shuttle Endeavour STS-123 liftoff
(video by H. Zenil on March 11, 2008)
This video recording was made from the vantage point of the Banana river, 6 miles from the Shuttle platform in a restricted area inside the Kennedy Space Center. The STS-123 was the 25th. flight to the International Space Station (ISS) and delivered a Japanese module and the Canadian Dextre robot.

 



Control room of the Arecibo telescope in Puerto Rico and M. Nolan, director of the
observatory in a visit with friend L. Doyle from SETI. January 2014.

 

 

 

Wolfram Science School trip to San Gimignano, Italy
(Summer, 2009)

From left to right school instructors: Hector Zenil, Jamie Williams, Paul-Jean Letourneau,
Tommaso Bolognesi, Jean Baetens. Among the participants: Ray Aschheim.

 


Héctor Zenil-Chávez, Personal Homepage 2006-2014

 


| BLOG
| PICTURES |
|
Math GenTree |
Google Scholar

 

OACC - Online Algorithmic Complexity Calculator

Algorithmic Nature
Group

Laboratoire de Recherche Scientifique LABORES

Shortest Universal Machine Implementation Contest

Selected Volumes

A Computable Universe

Irreducibility and
Computational Equivalence


Randomness Through Computation

 

Repositories

Papers in the ArXiv

Papers in PhilSci Archive

Papers in Econpaper

Papers in Nature Precedings

Papers in DBLP Bibliography Server

Demonstrations

OEIS sequences

Pictures

Videos

 

Algorithmic Nature Group

Leiden Center for Natural Computing

Weizmann Institute of Science

Cronin Lab

The Complex Systems Lab

Complex Systems Center, UV

Institut des Systèmes Complexes

Unit of Computational Medicine

Centre for Digital Philosophy

Research Group on Natural Computing

BET Lab

Luisi Synthetic Biology Lab

CoMPLEX Research Group

2020 Science, UCL, Cambridge, Microsoft

York Centre for Complex Systems Analysis

Sebastian Anhert Group

Cambridge Networks Network

Ard Louis research group, Oxford

CABDyN Complexity Centre

UCL Networks Research

The Francis Crick Institute

C3 UNAM

Systems and Networks Group, UCL

FQXi

List of Complex Networks groups in the UK

 

Other Links

Cellular Automata
Sources Repository

Visualizing Algorithms

APROS at CMU

Logic and Proofs
Open Learning Initiative

Online Handbook of Applied Cryptography

String Similarity Metrics

World of Symbols

Mondovortoj Centre for Computational Linguistics

Donald Knuth
Online Lectures

Complexification:
A Gallery of Computation

Claude Shannon Memorial
by Neil Sloane

Code Academy

Theory of Algorithmic Self-Assembly Review

Wang Tiles post

 

My Favorite Videos

Sydney Brenner on Turing's contributions to Biology

Stephen Wolfram at TED on Computable Universe Hunting

Leonard Susskind on QM, Condensates, QED and more

Raphael Bousso on Quantum Gravity and the Holographic Principle

Docudrama of Douglas Hofstadter, Daniel Dennett, Marvin Minsky

Incompleteness: A Personal Perspective by Cris Calude

Sean Carroll on Entropy and Complexity in the Universe

Scott Aaronson on Computational Complexity and Quantum Computing

What is Reality?

Tononi's Integrated Information Theory of Consciousness

Feynman Messenger Lectures at Cornell at Tuva Microsoft

Systems Biology lectures by Uri Alon

The Information Machine

Logic by Machine

Hamming on Hamming (Representation of Information, Coding theory)

Hamming on Information Theory

MIT lectures on Information, Entropy, Probability and Communication

Slippery Cellularities (artificial cells)

TEDx Lee Cronin: Making matter come alive

Networking chemistry: Lee Cronin at TEDxCERN

Martin Hanczyc: The line between life and not-life

Christoph Adami: Finding life we can't imagine

The Lambda Calculus, General Term Rewriting and Food Nutrition

Noether's theorem and symmetry breaking

ET Math: How different could it be? SETI

The secret army (the inmune system) explained by Nobel prizes