Searching for shortest and least programs

DOI10.1016/J.TCS.2019.10.011MaRDI QIDQ2286740zbMATH OpenOpenAlexWikidataFDO

Authors Cristian S. Calude, Sanjay Jain, Wolfgang Merkle, Frank Stephan

Publication date 22 January 2020

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2019.10.011

zbMATH Keywords

algorithmic information theoryBennett-shallow setKolmogorov complexityleast programrecursion theoryrecursive coding functionshortest programuniversal Turing machine

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Review text

Inspired by the existence of Solovay functions, the authors investigate coding functions. I.e. partial functions \(p\) so that \(M(p(x))=x\) for some Turing machine \(M\) and every \(x\) in the domain of \(p\). Then it is proved that for any plain or prefix-free universal machine \(U\), there is a recursive coding function \(f\) so that \(f(x)\) maps infinitely many strings to their least programs. They also look at some interesting properties. For example, a set is Bennett-deep for plain complexity in case for every recursive upper bound \(g\) for plain complexity \(C\) (or prefix-free complexity \(K\)), \(\lim_n g(A \upharpoonright n)-C(A \upharpoonright n)=\infty\) (or \(\lim_n g(A \upharpoonright n)-K(A \upharpoonright n)=\infty\)). They use recursive coding functions to characterize such sets.

Recommendations

• Coding with minimal programs
• Short lists with short programs in short time
• Enumerations including laconic enumerators
• Kolmogorov complexity and solovay functions
• Short lists with short programs from programs of functions and strings

Cites work

• A guided tour of minimal indices and shortest descriptions
• Algorithmic randomness and complexity.
• An incomplete set of shortest descriptions
• An introduction to Kolmogorov complexity and its applications
• Classical recursion theory. The theory of functions and sets of natural numbers
• Classical recursion theory. Vol. II
• Coding with minimal programs
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• Computability and randomness
• Computational depth and reducibility
• Computational depth: Concept and applications
• Computing a Glimpse of Randomness
• Depth, highness and DNR degrees
• Enumerations including laconic enumerators
• Enumerations of the Kolmogorov function
• Hierarchies of randomness tests
• scientific article; zbMATH DE number 4093436 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• scientific article; zbMATH DE number 1911266 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• Immunity and hyperimmunity for sets of minimal indices
• Information-theoretic characterizations of recursive infinite strings
• Limit-depth and DNR degrees
• Lowness and logical depth
• On approximate decidability of minimal programs
• On the polynomial depth of various sets of random strings
• On the size of machines
• Program size in restricted programming languages
• Randomness and universal machines
• Representation of left-computable \(\varepsilon \)-random reals
• Short lists for shortest descriptions in short time
• Short lists with short programs from programs of functions and strings
• Short lists with short programs in short time
• Short lists with short programs in short time -- a short proof
• Solovay functions and their applications in algorithmic randomness
• Three approaches to the quantitative definition of information^*
• Time-bounded Kolmogorov complexity and Solovay functions
• Universal recursively enumerable sets of strings

Cited in

(4)

• Short lists with short programs from programs of functions and strings
• Short lists with short programs in short time
• A computation model with automatic functions and relations as primitive operations
• Coding with minimal programs

This page was built for publication: Searching for shortest and least programs

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