Symmetry and correspondence of algorithmic complexity over geometric, spatial and topological representations

Hector Zenil*, Narsis A. Kiani, Jesper Tegnér

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

2 Scopus citations

Abstract

We introduce a definition of algorithmic symmetry in the context of geometric and spatial complexity able to capture mathematical aspects of different objects using as a case study polyominoes and polyhedral graphs. We review, study and apply a method for approximating the algorithmic complexity (also known as Kolmogorov-Chaitin complexity) of graphs and networks based on the concept of Algorithmic Probability (AP). AP is a concept (and method) capable of recursively enumerate all properties of computable (causal) nature beyond statistical regularities. We explore the connections of algorithmic complexity-both theoretical and numerical-with geometric properties mainly symmetry and topology from an (algorithmic) information-theoretic perspective. We show that approximations to algorithmic complexity by lossless compression and an Algorithmic Probability-based method can characterize spatial, geometric, symmetric and topological properties of mathematical objects and graphs.

Original languageEnglish (US)
JournalEntropy
Volume20
Issue number7
DOIs
StatePublished - Jul 1 2018

Keywords

  • Algorithmic coding theorem
  • Algorithmic probability
  • Information content
  • Kolmogorov-Chaitin complexity
  • Molecular complexity
  • Polyhedral networks
  • Polyominoes
  • Polytopes
  • Recursive transformation
  • Shannon entropy
  • Symmetry breaking
  • Turing machines

ASJC Scopus subject areas

  • Information Systems
  • Mathematical Physics
  • Physics and Astronomy (miscellaneous)
  • Electrical and Electronic Engineering

Fingerprint

Dive into the research topics of 'Symmetry and correspondence of algorithmic complexity over geometric, spatial and topological representations'. Together they form a unique fingerprint.

Cite this