Computable Model Discovery and High-Level-Programming Approximations to Algorithmic Complexity

DOI10.1016/J.TCS.2022.05.026MaRDI QIDQ6386483arXivWikidataFDO

Authors Vladimir Lemus, Eduardo Acuña-Yeomans, Víctor Zamora, Francisco Hernández-Quiroz, Hector Zenil

Publication date 22 December 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2022.05.026

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

arXiv classification

cs.IT cs.LO math.IT

Abstract: Motivated by algorithmic information theory, the problem of program discovery can help find candidates of underlying generative mechanisms of natural and artificial phenomena. The uncomputability of such inverse problem, however, significantly restricts a wider application of exhaustive methods. Here we present a proof of concept of an approach based on IMP, a high-level imperative programming language. Its main advantage is that conceptually complex computational routines are more succinctly expressed, unlike lower-level models such as Turing machines or cellular automata. We investigate if a more expressive higher-level programming language can be more efficient at generating approximations to algorithmic complexity of recursive functions, often of particular mathematical interest.

This page was built for publication: Computable Model Discovery and High-Level-Programming Approximations to Algorithmic Complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6386483)