On Approximate Decidability of Minimal Programs

DOI10.1145/2799561zbMath1347.68096arXiv1409.0496OpenAlexW1892482121MaRDI QIDQ2828213

Marius Zimand, Jason Teutsch

Publication date: 24 October 2016

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.0496

zbMATH Keywords

Kolmogorov complexityminimal indicesnumberingsfrequency computationlist approximations

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursive functions and relations, subrecursive hierarchies (03D20) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30)

Related Items (4)

Enumerations including laconic enumerators ⋮ Short lists with short programs from programs of functions and strings ⋮ Searching for shortest and least programs ⋮ On Approximate Decidability of Minimal Programs

Cites Work

• Unnamed Item
• Short lists for shortest descriptions in short time
• Index sets and universal numberings
• An easy priority-free proof of a theorem of Friedberg
• Immunity and hyperimmunity for sets of minimal indices
• A guided tour of minimal indices and shortest descriptions
• Classical recursion theory. The theory of functions and sets of natural numbers
• Short lists with short programs in short time
• On the Turing degrees of minimal index sets
• Enumerations including laconic enumerators
• On Approximate Decidability of Minimal Programs
• Game Arguments in Computability Theory and Algorithmic Information Theory
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Algorithmic Minimal Sufficient Statistic Revisited
• Program size in restricted programming languages
• Short Lists with Short Programs in Short Time – A Short Proof
• An incomplete set of shortest descriptions
• Enumerations of the Kolmogorov function
• On the size of machines
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• On Computable Numbers, with an Application to the Entscheidungsproblem
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: On Approximate Decidability of Minimal Programs